4.5Binary Search Trees

Trees

A data structure that consists of nodes in a parent/child relationship

앞서 살펴본 Singly/Doubly Linked List나 Stack, Queue와 Tree의 차이는, Tree는 선형적이지 않다는 것이다. 즉, 이전 노드가 하나 이상의 다음 노드를 가리킬 수 있다.

이미지 출처 : #

또, 부모/자식 관계는 양방향이 아니며, 형제 간에도 서로를 가리키거나 할 수 없다. 물론 그런 데이터 구조도 만들 수는 있겠지만 그런 경우는 Tree라고 부르지 않는다. Tree의 각 노드 타입에 대한 정의를 내리면 아래와 같다.

• Root: 트리 데이터 구조의 가장 위에 있는 노드
• Child: 루트로부터 멀어지면서 다른 노드와 직접적으로 연결되어 있는 노드
• Parent: 자식 노드와 직접적으로 연결되어 있는, 루트와 보다 가까운 노드
• Siblings: 같은 부모 노드를 가진 노드들의 통칭
• Leaf: 자식 노드가 없는 노드
• Edge: 하나의 노드와 다른 노드 사이의 연결(위의 도식에서 화살표에 해당)

웹 개발 관련 공부를 한다면 트리는 아주 자주 쓰이는 데이터 구조다.

• HTML DOM은 document로부터 시작해 document.body, document.body.children[0](이 안에 <div>가 있고 <h2>가 있고...)식으로 구성된다.
• 네트워크 라우팅에서 브로드캐스트 기법은 브로드캐스트 도메인 안에 있는 모든 네트워크 장비들에게 통신을 보내는데, 부모-자식 노드들 간의 관계로 볼 수 있다.
• 컴파일러들은 파싱을 추상 구문 트리(Abstract Syntax Tree) 형태로 한다.
• 인공지능에서 minimax tree는 게임의 진행을 특정 수에 따른 경우의 수들로 나누어가며 그리는 트리다.
• 운영체제의 폴더 구조도 트리 구조다.
• JSON은 트리 구조다.

Binary Search Tree

트리에는 종류가 아주 많으나, 우리는 여기서 Binary Search Tree를 살펴보려고 한다. Binary Tree(이진 트리)는 하나의 부모가 최대 2개의 자식을 가지는 트리 구조다. 그 중에서도 Binary Sarch Tree는 데이터 검색을 위해 쓰는 트리 구조로, 루트로부터 자식 노드들까지가 모두 정렬이 되어 있는 이진 트리다.

• 부모 노드는 최대 2개의 자식 노드를 가진다.
• 왼쪽 자식 노드는 항상 부모 노드 이전 순서의 노드다.(ex. 값이 적다)
• 오른쪽 자식 노드는 항상 부모 노드 이후 순서의 노드다.(ex. 값이 크다)

이미지 출처 : #

이렇게 정렬이 되어 있으면, 찾고자 하는 데이터의 이전/이후 데이터인지만 몇번 비교하며 트리를 찾아 내려가면 O(log n)으로 아주 빠르게 데이터를 찾을 수 있다.

자바스크립트 구현

노드에는 value, left, right가 필요하고 Binary Search Tree에는 root 노드가 필요하다.

javascript
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
}

const tree = new BinarySearchTree();
tree.root = new Node(10);
tree.root.right = new Node(15);
tree.root.left = new Node(7);
tree.root.left.right = new Node(9)
// ...

물론 직접 이렇게 정렬하며 new Node()로 추가하는 것은 바람직하지 않다. Insert 메소드로 노드를 자동으로 추가해보자.

Insert 메소드 추가하기

수도코드를 짠다면 아래와 같이 된다:

• 노드를 생성한다.
• 루트 노드에서 시작해, 루트가 없다면 루트에 새로 생성한 노드를 할당한다.
• 루트가 있다면, 값이 새로 생성한 노드보다 큰지, 작은지를 비교해서 크면 오른쪽으로, 작으면 왼쪽의 노드를 체크한다.
• 반복해서 해당 방향에 노드가 없다면 추가한다.

javascript
class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    const newNode = new Node(value);
    if(this.root === null){
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while(true){
        if(value === current.value) return undefined; // 중복값에 의한 무한루프 방지
        if(value < current.value){
          if(current.left === null){
            current.left = newNode;
            return this;
          } else {
            current = current.left;
          }
        } else if(value < current.value){
          if(current.right === null){
            current.right = newNode;
            return this;
          } else {
            current = current.right;
          }
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);

Find 메소드 추가하기

수도코드를 짠다면 아래와 같이 된다:

• 루트 노드에서 시작해서, 루트가 없으면 찾을 것도 없다.
• 루트 노드가 있다면, 루트 노드와 비교해서 같으면 찾은 것이고, 없다면 값을 비교한다.
• 비교하는 값이 크다면 오른쪽으로 가고, 이 과정을 반복한다. 작다면 왼쪽으로 가고, 반복한다.
• 비교하는 값과 찾고자 하는 값이 같다면 찾은 것이고, 작거나 큰데 해당 위치에 없다면 데이터가 없는 것이다.

javascript
class BinarySearchTree {
  // 다른 메소드들...
  find(value){
    if(this.root === null) return false;
    let current = this.root, found = false;
    while(current && !found){
      if(value < current.value){
        current = current.left;
      } else if(value > current.value){
        current = current.right;
      } else{
        found = true;
      }
    }
    if(!found) return undefined;
    return current;
  }
}

BST의 Big O

BST의 데이터 추가와 검색은 모두 평균적으로 O(log n)이다. BST는 노드 수가 2배가 되어도 데이터 추가/검색에 필요한 단계는 딱 1만큼만 늘 정도로 데이터 추가와 검색에 효율적이다.

하지만 이 O(log n)은 보장된 값은 아니다. 예를 들어, 아래와 같이 불합리해보이는 BST도 충분히 가능하다.

이미지 출처 : #

다만 평균적으로 BST만큼 검색이 빠르면서도 자료 입력과 삭제(이후 개인 탐구에서 구현해보자)도 효율적인 경우는 드물고, 그렇기에 이진 탐색 트리는 종종 쓰인다. 위와 같은 극단적인 경우를 막고자 트리의 입력, 삭제 단계에 트리 전체의 균형을 맞추는 이진 탐색 트리의 일종인 AVL Tree라는 것도(역시 이후 개인 탐구에서 구현해보자) 제안된다. 또, 다음 포스팅에서 살펴볼 Binary Heap도 이런 문제를 해결할 수 있다.

---

🤠 개인 탐구

강의에선 연습문제로 remove, findSecondLargest, isBalanced 메소드들을 구현하라고 한다. 한번 구현해보자.

remove 구현하기

제거는 삽입에 비해 좀 더 복잡한데, 그 이유는 자식의 존재 때문이다. 제거할 대상 노드가 리프 노드(자식 없음)라면 그냥 해당 노드를 제거하면 되지만, 자식이 하나, 또는 둘 있고 그 자식에게 자식이 또 있는 경우가 있다면 해당 노드를 대체할 자식 노드를 가져와야하기 때문이다.

경우의 수를 정리하자면 이렇게 된다:

1. 리프 노드(자식 없음): 그냥 해당 노드 삭제
2. 하나의 자식만 있는 노드: 자식 노드로 대체
3. 두 개의 자식이 있는 노드: 오른쪽 서브트리의 최솟값 노드를 현재 노드의 자리에 대체하고, 해당 노드를 재귀적으로 삭제

재귀적 삭제 로직이 들어가기 때문에, private method를 활용해 remove()안에서만 실행하는 방식으로 해결하는 것이 깔끔하다.

javascript
remove(value){
  this.root = this._removeNode(this.root, value);
}

_removeNode(current, value){
  if(!current) return null;

  if(value < current.value){
    current.left = this.removeNode(current.left, value);
    return current;
  } else if (value > current.value){
    current.right = this._removeNode(current.right, value);
    return current;
  } else {
    if(!current.left && !current.right) return null;
    if(!current.right) return current.right;
    if(!current.left) return current.left;
    let successor = this._getMinValueNode(current.right);
    current.value = successor.value;
    current.right = this._removeNode(current.right, successor.value);
    return current;
  }
}

_getMinValueNode(node){
  while(node.left){
    node = node.left;
  }
  return node;
}

findSecondLargest 구현하기

BST의 가장 큰 값은 항상 오른쪽 맨 끝에 있는 노드다. 두번째로 큰 값은 둘 중 하나다:

1. 가장 큰 노드가 리프라면, 그 부모
2. 가장 큰 노드의 왼쪽 서브트리에서 가장 큰 값

따라서 이 두 가지 케이스를 구하면 된다. 구현 과정에서 필연적으로 "가장 큰 값"을 구하는 함수도 쓰게 된다.

javascript
findSecondLargest(){
  if(!this.root || (!this.root.left && !this.root.right)){
    return null; // 트리에 노드가 하나 이하인 경우
  }

  let current = this.root;

  while(current){
    // 1번 케이스: 가장 큰 노드가 리프라면, 그 부모
    if(current.right && !current.right.left && !current.right.right){
      return current.value;
    }
    // 2번 케이스: 가장 큰 노드의 왼쪽 서브트리에서 가장 큰 값
    if(!current.right && current.left){
      return this._findLargest(current.left).value;
    }
    current = current.right;
  }
  return null;
}

findLargest(node){
  while(node.right){
    node = node.right;
  }
  return node;
}

isBalanced 구현하기

트리의 모든 리프 노드 또는 단일 자식을 가진 노드들의 깊이 차이가 1 이하인 트리를 Balanced Tree라고 부른다면, 이 Balanced Tree 여부를 확인할 수 있는 isBalanced 메소드를 구현하라는 문제다. 즉, 가장 얕은 리프 노드와 가장 깊은 리프 노드의 깊이 차이가 1을 초과하면 false인 케이스다.

재귀적으로 깊이를 구하는 함수를 만들어 해결할 수 있다.

javascript
isBalanced(){
  const checkHeight = (node) => {
    if(!node) return 0;

    const leftHeight = checkHeight(node.left);
    if(leftHeight === -1) return -1;

    const rightHeight = checkHeight(node.right);
    if(rightHeight === -1) return -1;

    if(Math.abs(leftHeight - rightHeight) > 1) return -1;

    return Math.max(leftHeight, rightHeight) + 1;
  }

  return checkHeight(this.root) !== -1;
}

AVL 트리 구현하기

AVL Tree는 항상 균형을 유지하도록 자동으로 조정되는 트리로, 만든 사람들의 이름인 Adelson-Velsky and Landis를 따와서 붙은 이름이다.

이 트리가 균형을 유지하는 방식은,

• 각 노드마다 균형 인수(balance factor)를 저장하여
  • 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이의 차이를 기록한다.
  • 이 값이 -1, 0, 1이면 균형 잡힌 것(isBalanced)으로 본다.
  • 그 외에는 회전(Rotation)을 통해 균형을 자동으로 조정한다.

지금까지 구현한 이진 탐색 트리는 예를 들어 이런 경우 쉽게 Skewed Tree가 되어 의미를 잃는다.

javascript
binarySearchTree.insert(1).insert(2).insert(3)

위의 추가문은 아래와 같은, singly linked list나 다름없는 비효율적인 트리를 만든다.

bash
1
 \
  2
   \
    3

탐색, 삽입, 삭제가 모두 O(N)인 지극히 비효율적인 트리로, AVL 트리로 구현한다면 O(log n) 균형을 유지할 수 있다.

AVL 트리의 핵심은 아래의 회전이다.

또, 노드도 left, right뿐 아니라 균형 인수를 계산해야하므로 height를 가진다.

javascript
class AVLNode {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor(){
    this.root = null;
  }

  insert(value){
    this.root = this._insert(this.root, value);
  }

  _insert(node, value){
    if(!node) return new AVLNode(value);

    if(value < node.value){
      node.left = this._insert(node.left, value);
    } else if (value > node.value){
      node.right = this._insert(node.right, value);
    } else {
      return node;
    }

    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));

    const balance = this._getBalance(node);

     // LL
    if (balance > 1 && value < node.left.value) {
      return this._rotateRight(node);
    }

    // RR
    if (balance < -1 && value > node.right.value) {
      return this._rotateLeft(node);
    }

    // LR
    if (balance > 1 && value > node.left.value) {
      node.left = this._rotateLeft(node.left);
      return this._rotateRight(node);
    }

    // RL
    if (balance < -1 && value < node.right.value) {
      node.right = this._rotateRight(node.right);
      return this._rotateLeft(node);
    }

    return node;
  }

  // 회전 함수들
  _rotateLeft(z) {
    const y = z.right;
    const T2 = y.left;

    y.left = z;
    z.right = T2;

    z.height = 1 + Math.max(this._getHeight(z.left), this._getHeight(z.right));
    y.height = 1 + Math.max(this._getHeight(y.left), this._getHeight(y.right));

    return y;
  }

  _rotateRight(z) {
    const y = z.left;
    const T3 = y.right;

    y.right = z;
    z.left = T3;

    z.height = 1 + Math.max(this._getHeight(z.left), this._getHeight(z.right));
    y.height = 1 + Math.max(this._getHeight(y.left), this._getHeight(y.right));

    return y;
  }

   _getHeight(node) {
    return node ? node.height : 0;
  }

  _getBalance(node) {
    return node ? this._getHeight(node.left) - this._getHeight(node.right) : 0;
  }
}