ES6 이진 탐색 트리 구현하기, 어떻게 특정 값을 빠르게 찾을 수 있을까? (Binary Search Tree, BST)

이진 탐색 트리 (Binary Search Tree with ES6)

트리 구조에 대해서는 많이 들어보았다고 생각한다.

어렵게 생각할 것도 아닌 그냥 루트(root)노드에서 하위 노드로 계층 구조를 갖는 것을 트리라고 보면된다.

윈도우 파일시스템 구조처럼 C드라이브 하위에 windows디렉토리, program files디렉토리 등이 있고 program files디렉토리 하위에 Java디렉토리가 있는 등 이런 구성이 트리다.

각설하고. 프로그래밍에서 노드 2개 이하로 제한하는 방식을 이용해 이진 탐색 트리(BST)라는 것을 만들었다.

노드가 2개이하라는 특징 덕분에 프로그래밍에서 특정 값 검색을 빠르게 할 수 있게 되었다.

이진 탐색 트리는 루트 노트를 기준으로 루트 노트보다 작은 값은 왼쪽 하위노드로, 루트 노트보다 큰 값은 오른쪽 하위노드로 설정하는 방식이다.

---

이진 탐색 트리 구현 

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());

결과 콘솔

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 

하나하나 이해해본다.

이진 탐색 트리에서 insert(data) 메서드를 살펴보면 당연히 루트노드가 없을 때는 처음 삽입(insert)한 것이므로 루트노드로 지정하면 된다.

루트노드가 있을 때는 임시로 부모노드(parentNode)로 설정하면서 삽입할 값이 부모노드보다 작으면 왼쪽 노드, 부모노드보다 크면 오른쪽 노드로 가는 룰을 반복하면서 삽입할 위치로 찾아간다.

inOrder()메서드는 이진 탐색 트리에서 탐색하는 방법으로 전위 순회, 중위 순회, 후위 순회가 있는데 그 중 중위 순회를 나타낸 것으로 중위 순회는 왼쪽자식노드->현재노드->오른쪽자식노드 순으로 탐색하는 것이다.

따라서 저절로 오름차순으로 탐색하고 console.log를 찍기 때문에 오름차순으로 값이 출력된다.

find()메서드는 해당 값을 검색하는 메서드로 기존 이진 탐색 트리의 룰대로 노드를 찾아 내려가다가 해당 값을 가진 노드를 만나면 그 노드를 반환하고 없으면 null을 반환한다.

삭제가 조금 어려울 수 있는데 remove()메서드는 data를 가진 노드를 삭제하기 위해 호출용으로 메서드를 부른 것이다.

removeNode()의 알고리즘을 잘 생각해야한다.

자식이 없는 leaf노드 같은 경우에는 그냥 해당 노드를 제거해버리면 된다.

하지만 탐색한 노드가 자식이 있는 경우는 또 3가지다.

왼쪽 자식만 있는 경우는 해당 노드를 삭제하고 왼쪽 자식노드를 그 자리로 옮겨주면 된다.

오른쪽 자식만 있는 경우는 해당 노드를 삭제하고 오른쪽 자식노드 그 자리로 옮겨주면 된다.

자식이 둘 다 있을 때는 둘 중에 하나를 선택해야한다.

왼쪽 노드에서 가장 큰 노드를 해당 노드 위치로 옮기든지, 오른쪽 노드에서 가장 작은 노드를 해당 노드 위치로 옮기든지.

위 소스에서는 오른쪽 노드에서 가장 작은 노드를 찾아 해당 노드 위치로 옮긴다.

이해를 돕기 위해 처음 노드 삽입을 완료했을 때 그림을 첨부한다.

45를 제거할 때 양 쪽에 자식 노드가 존재하므로 45를 제거할 때 오른쪽에서 제일 작은 노드인 65를 그자리로 올리고 원래 45가 있을 노드의 오른쪽 자식노드에서 65라는 값을 가진 노드를 찾아 제거하는 방법이다.

참고 도서

- Data Structures and Algorithms with Javascript