트리

function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
}

function BST() {
  this.root = null;
}

BST.prototype.insert = function (data) {
  var node = new Node(data, null, null);
  // 만약 빈 트리라면
  if (this.root === null) {
    this.root = node;
  } else {
    var current = this.root;
    var parent;

    while (true) {
      parent = current;
      // 데이터가 현재 노드의 데이터보다 작을 경우
      if (data < current.data) {
        current = current.left;
        // 현재 노드의 데이터가 null일 경우
        if (current === null) {
          // 현재 위치에 노드 삽입
          parent.left = node;
          break;
        }
      } else {
        current = current.right;
        if (current === null) {
          parent.right = node;
          break;
        }
      }
    }
  }
}

BST.prototype.delete = function (data) {
  var current = this.search(data);
  var parent = this.getParent(current);

  if (current.right === null && current.left === null) { // 자식이 없는 노드를 지울 떄
    // 노드를 null로 만든다
    if (parent.left.data === data) {
      parent.left = null;
    } else {
      parent.right = null;
    }
  } else if (current.right !== null && current.left !== null) { // 자식이 둘 다 있을 때
    // 오른쪽 자식 중에서 가장 작은 값을 구한다
    var min = this.getMin(current.right);
    // 최소값을 복사한다
    var tempNode = min;
    // 최소값의 부모 노드를 구한다
    var minParent = this.getParent(min);

    // 최소값 노드와 부모 노드간의 연결을 끊는다
    if (minParent.right.data === min.data) {
      minParent.right = null;
    } else {
      minParent.left = null;
    }

    // 지우려고 하는 데이터와 최소값 노드의 데이터를 교체한다
    current.data = tempNode.data;
    // 최소값 노드에 자식노드를 연결해 준다
    current.right = tempNode.right;
  } else { // 자식이 하나만 있을 때
    // 삭제하려는 노드의 자식노드를 구한다
    var child = current.left === null ? current.right : current.left;
    // 삭제하려는 노드의 부모노드와 삭제하려는 노드의 자식노드를 연결한다
    if (parent.left == current) {
      parent.left = child;
    } else {
      parent.right = child;
    }
  }
}

BST.prototype.search = function (data) {
  var current = this.root;
  while (current.data !== data) {
    if (current.data > data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return current;
}

BST.prototype.getParent = function (node) {
  var current = this.root;
  var parent;

  while (current.data !== node.data) {
    parent = current;

    if (node.data < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return parent;
}

BST.prototype.getMin = function (node) {
  var current = node;
  while (current.left !== null) {
    current = current.left;
  }
  return current;
}

BST.prototype.getMax = function (node) {
  var current = node;
  while (current.right !== null) {
    current = current.right;
  }
  return current;
}

// 전위
BST.prototype.preOrder = function (node) {
  console.log(node.data);
  if (node.left !== null) {
    this.preOrder(node.left);
  }
  if (node.right !== null) {
    this.preOrder(node.right);
  }
}

// 중위
BST.prototype.inOrder = function (node) {
  if (node.left !== null) {
    this.inOrder(node.left);
  }
  console.log(node.data);
  if (node.right !== null) {
    this.inOrder(node.right);
  }
}

// 후위
BST.prototype.postOrder = function (node) {
  if (node.left !== null) {
    this.postOrder(node.left);
  }
  if (node.right !== null) {
    this.postOrder(node.right);
  }
  console.log(node.data);
}

var tree = new BST();
tree.insert('F');
tree.insert('B');
tree.insert('G');
tree.insert('A');
tree.insert('D');
tree.insert('I');
tree.insert('C');
tree.insert('E');
tree.insert('H');

// tree.preOrder(tree.root); // F, B, A, D, C, E, G, I, H
// tree.inOrder(tree.root); // A, B, C, D, E, F, G, H, I
// tree.postOrder(tree.root); // A, C, E, D, B, H, I, G, F

tree.delete('D')
// tree.inOrder(tree.root); // A, B, C, E, F, G, H, I
tree.delete('F');
tree.inOrder(tree.root); // A, B, C, E, G, H, I

class BinaryHeap {
  constructor() {
    this.heap = [30, 20, 10, 7, 9, 5]
  }

  // 힙에 요소 추가
  insert(data) {
    this.heap.push(data)
    this.bubbleUp();
  }

  // 일반 배열을 힙으로 구성
  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      let element = this.heap[index];
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];

      // 부모가 요소보다 크거나 같을 경우 루프 중단
      if (parent >= element) break;

      // 부모와 요소 교환
      this.heap[index] = parent;
      this.heap[parentIndex] = element;
      index = parentIndex;
    }
  }

  // 루트 노드를 추출하고 정렬
  extractMax() {
    const max = this.heap[0];
    // 힙의 첫번째 요소를 마지막 요소로 초기화
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return max
  }

  sinkDown(current) {
    let left = 2 * current + 1;
    let right = 2 * current + 2;
    let largest = current;
    const length = this.heap.length;

    // 최상단 루트의 값과 왼쪽, 오른쪽 자식의 값과 비교를 해 큰값을 largest 변수에 넣는다.
    if (left <= length && this.heap[left] > this.heap[largest]) {
      largest = left
    }
    if (right <= length && this.heap[right] > this.heap[largest]) {
      largest = right
    }

    // 가장 큰 값의 인덱스가 현재 인덱스와 같지 않을 경우
    if (largest !== current) {
      // 가장 큰 값의 인덱스와 현재 인덱스의 값을 바꿔 준다.
      [this.heap[largest], this.heap[current]] = [this.heap[current], this.heap[largest]]
      // 최대 힙이 다 구성되지 않은 상태이니, 구성할 때까지 재귀적 호출을 한다.
      this.sinkDown(largest)
    }
  }

}

const heap = new BinaryHeap();
heap.insert(90);
heap.insert(50);
// console.log(heap); //BinaryHeap { heap: [ 90, 50, 30, 20, 9, 5, 10, 7 ] }
heap.extractMax();
console.log(heap); //BinaryHeap { heap: [ 50, 30, 20, 9, 5, 10, 7 ] }