Javascript로 이진탐색트리 구현하기

//나보다 작은애들이 왼쪽 나보다 큰애들이 오른쪽
class BinarySearchTree {
  root = null;
  length = 0;
  #insert(node,value){
    if(node.value > value){
      // 루트 노드보다 작으면
      if(node.left){
        if(node.left.value === value){
          console.log(`${value}값은 이미 존재하는 값입니다.`)
          return
        }
        this.#insert(node.left, value);
      }else{
        node.left = new Node(value);
        this.length++;
      }
    }else{
      // 루트 노드보다 크면
      if(node.right){
        if(node.right.value === value){
          console.log(`${value}값은 이미 존재하는 값입니다.`)
          return
        }
        this.#insert(node.right, value);
      }else{
        node.right = new Node(value);
        this.length++;
      }
    }
  }

  insert(value){  
    //어떤 값을 넣으려할때, 어디에 넣을지 모르겠다.
    //그래서 왼팔 오른팔한테 맡긴다.
    // 만약 왼팔 오른팔이 없으면 거기다 넣는다.
    if(!this.root){
      this.root = new Node(value);
      this.length ++;
    }else{
      this.#insert(this.root, value);
    }
  }

  #search(node,value){
    if(node.value > value){
      if(!node.left){
        return null;
      }
      if(node.left.value === value){
        return node.left;
      }
      return this.#search(node.left, value);
    }else{
      if(!node.right){
        return null;
      }
      if(node.right.value === value){
        return node.right;
      }
      return this.#search(node.right, value);
    }
  };

  search(value){
    if(!this.root){
      return null
    }
    if(this.root.value === value){
      return this.root;
    }
    return this.#search(this.root, value);
  }
  
  #remove(node,value){
    if(!node){
      //제거할 값이 bst에 존재하지 않는경우
      return null; //지울 값이 존재 안하면 false, 존재하면 true
    }
    if(node.value === value){ //자식 입장
      //지울값을 찾은경우
      if(!node.left && !node.right){
        //leaf
        this.length--;
        return null;
      }
      if(!node.right){
        this.length--;
        return node.left;
      }
      if(!node.left){
        this.length--;
        return node.right;
      }
      if(node.left && node.right){
        let exchange = node.left;
        while(exchange.right){
          exchange = exchange.right;
        }
        let temp = node.value;
        node.value = exchange.value;
        exchange.value = temp; 
        node.left = this.#remove(node.left,temp);
        return node;
      }

    }else{
      if(node.value > value){//부모 입장
        if(!node.left){
          return null;
        }
        node.left = this.#remove(node.left, value);
        return node;
      }else{
        if(!node.right){
          return null;
        }
        node.right = this.#remove(node.right, value);
        return node;
    }

  }
}
  remove(value){
    //1. leaf(양팔 x) => 제거
    //2. leaf x 왼팔이 없다 => 오른팔 끌어올리기
    //3. leaf x 오른팔이 없다 => 왼팔 끌어올리기
    //3. leaf x 양팔 다 있다. 왼팔에서 가장 큰 애와 바꾼다, leaf를 지운다.
    if(!this.root){
      return null;
    }else{
      this.root = this.#remove(this.root, value);
      return this.length;
    }
  }
}

class Node{ 
  left = null;
  right = null;
  constructor(value) {
    this.value = value;
  }
}
const bst = new BinarySearchTree;
bst.insert(8);
bst.insert(10);
bst.insert(10);
bst.insert(3);
bst.insert(1);
bst.insert(6);
bst.insert(7);
bst.insert(4);
bst.insert(14);
bst.insert(13);
console.log('remove',bst.remove(8));
console.log('remove',bst.remove(10));

 

이진트리는 자식이 최소 0개에서 최대 2개를 가진다.

 

 

이진 트리의 종류

• Full - 모든 자식의 개수가 0이나 2
• Perfect - leaf가 아닌 노드들은 모두 자식이 2개여야하고 leaf들이 모두 같은 level 이어야한다., 꽉찬 삼각형 형태여야 한다.
• Complete - 왼쪽 부터 데이터를 채워 나가는 형태를 의미한다.
• Degenerate - 자식노드가 하나로 이어져있는 형태 (마지막 노드 제외, 가장 비효율적(Linked List와 동일 구조)) 
• Balanced(AVL트리, R/B트리) - 특정 노드를 기준으로 왼쪽과 오른쪽노드의 최대 길이의 차(diff)가 0또는 1이어야 한다.(모든 노드에 해당해야함)

 

이진 탐색트리에서는 remove시 주의해야할 조건

remove 하고자 하는 노드를 기준으로

1. leaf(자식노드가 없을때): 제거

2. 자식 노드가 왼쪽 노드 하나일때 : 왼쪽 노드를 끌어올리기

3. 자식 노드가 오른쪽 노드 하나일때 : 오른쪽 노드를 끌어올리기

4. 자식 노드가 왼쪽 오른쪽 두개 일때 : 지우고자 하는 노드의 왼쪽노드에서 가장 오른쪽 노드에 해당하는 노드를 자기자신과 바꾸고 기존의 자기자신은 삭제