Binary Search Tree

Binary Search Tree??

이진 탐색 트리(이진 탐색과 비슷?) 혹은 이진 트리라고 한다. 이 트리는 자식노드가 최대 두개로 구성되어 있다. 그래서 왼쪽 자식 오른쪽 자식으로 분류한다. 모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의한다.

이진트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 나뉜다.

• 완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
• 정 이진 트리 : 각 노드가 0개 또는 2개의 자식 노드를 가지고 있다.
• 포화 이진 트리 : 정 이진 트리이면서, 완전 이진 트리인 경우 이다. 마지막 레벨까지 모든 노드가 차 있어야 한다.

☝️ 포화 이진 트리
☝️ 완전 이진 트리
☝️ 정 이진 트리

class Node {
  constructor(data, left = null, right = null){
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor(){
    this.root = null;
  }
  add(data){
    const node = this.root;
    if(node === null){
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function(node){
        if(data < node.data){
          if(node.left === null){
            node.left = new Node(data);
            return;
          } else if(node.left !== null){
            return searchTree(node.left);
          }
        } else if(data > node.data){
          if(node.right === null){
            node.right = new Node(data);
            return;
          } else if(node.right !== null){
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }