알고리즘 11 검색트리 | 이진 탐색 트리 | JS

Dynamic Set

• 여러 개의 키(key)를 저장
• 다음과 같은 연산들을 지원하는 자료구조
  insert: 새로운 키의 삽입
  search: 키 탐색
  delete: 키의 삭제
• ex) 심볼 테이블

• 정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우
  insert, search, delete 중 적어도 하나는 O(n)

• 좀 더 효율적인 두 가지 방향
  1. 이진탐색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 등의 트리에 기반한 구조들
  2. Direct Address Table, 해쉬 테이블 등

검색 트리 | Search tree

• Dynamic set을 트리의 형태로 구현
• 일반적으로 search, insert, delete 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가짐
• 이진검색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리, B-트리 등

이진 탐색 트리 | Binary Search Tree(BST)

• 이진 트리이면서
• 각 노드에 하나의 키를 저장
• 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.
• 시간복잡도: O(h) = O(logN)
  (*h = tree의 높이, *N = 노드의 갯수)
• 시간복잡도(최악): O(N)
  (*N = 노드의 갯수)
  최악의 경우는 이진트리의 높이가 N인 경우 즉, 연결 리스트의 모양을 띄는 트리

Binary Heap vs Binary Search Tree

• Binary Heap
  : 완전 이진 트리
  : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같음(최대 힙의 경우)
  : 대소 관계가 수직적(상하)
• Binary Search Tree
  : 이진 트리
  : 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작거나 같고, 오른쪽 자식 노드는 부모보다 크거나 같음
  : 대소 관계가 수평적(좌우)

class Node{
  constructor(data, left, right){
    this.data = data;
    this.left = left;
    this.right = right;
  }
  show(){
      return this.data;
  }
}
 
//Binary Search Tree
class BST{
     constructor(){
      this.root = null;
    }
  
    getRoot(){
      return this.root;
    }
  
    insert(data){
    //새로운 Node 생성
    let n = new Node(data, null, null);
    //트리에 루트 노드가 없으면 생성한 노드가 루트 노드
    if(this.root == null){
      this.root = n;
    }
    else{
      //current에 루트 노드를 가져옴
      let current = this.root;
      let parent;
      while(true){
        parent = current;
        if(data < current.data){
          current = current.left;
          if(current == null){
            parent.left = n;
            break;
          }
        }
        else{
          current = current.right;
          if(current == null){
            parent.right = n;
            break;
          }
        }
      }
    }
  }
  
  inOrder(node){
    if(!(node == null)){
      this.inOrder(node.left);
      console.log(node.show());
      this.inOrder(node.right);
    }
  }
  
  find(data){
    let current = this.root;
    while(current.data != data){
      if(data < current.data){
        current = current.left;
      }
      else{
        current = current.right;
      }
      if(current == null){
        return null;
      }
    }
    return current;
  }
  remove(data){
    this.root = this.removeNode(this.root, data);
  }
  removeNode(node, data){
    if(node == null){
      return null;
    }
    if(data == node.data){
      //자식이 없을 때
      if(node.left == null && node.right == null){
        return null;
      }
      //왼쪽 자식이 없을 때
      if(node.left == null){
        return node.right;
      }
      //오른쪽 자식이 없을 때
      if(node.right == null){
        return node.left;
      }
      //둘 다 자식이 있을 때
      let tempNode = this.getSmallest(node.right);
      node.data = tempNode.data;
      node.right = this.removeNode(node.right, tempNode.data);
      return node;
    }
    else if(data < node.data){
      node.left = this.removeNode(node.left, data);
      return node;
    }
    else{
      node.right = this.removeNode(node.right, data);
      return node;
    }
  }
  getSmallest(node){
    let current = node;
    while(!(current.left == null)){
      current = current.left;
    }
    return current;
  }
}
 
const nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(15);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(21);
nums.insert(40);
nums.insert(44);
nums.insert(1);
nums.insert(65);
nums.inOrder(nums.getRoot());//1, 3, 15, 21, 23, 37, 40, 44, 45, 65, 99
console.log("==========");
console.log(nums.find(45)); 
console.log(nums.find(2));
nums.remove(45);
nums.inOrder(nums.getRoot());

• Result

1 
3 
15 
21 
23 
37 
40 
44 
45 
65 
99 
========== 
{"data":45,"left":{"data":37,"left":null,"right":{"data":40,"left":null,"right":{"data":44,"left":null,"right":null}}},"right":{"data":99,"left":{"data":65,"left":null,"right":null},"right":null}} 
null 
1 
3 
15 
21 
23 
37 
40 
44 
65 
99 

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
ES6 이진 탐색 트리 구현하기, 어떻게 특정 값을 빠르게 찾을 수 있을까? (Binary Search Tree, BST)

Photo by Michael Dziedzic on Unsplash