BST - Binary Search Tree

 

 

요즘 프로그래밍을 공부하는 사람들을 만나면, 다들 '자료구조 = 코딩테스트 준비' 라는 생각을 하고 있는 것 같습니다.

저는 수학에 사칙연산이 기본이라면, 코드를 작성할 때는 자료구조가 그 역할을 한다고 생각하는데요.

이번에는 다양한 트리 중에 이진 검색 트리를 살펴보겠습니다.

 

 

 

---

 

 

1.  BST 란?

Binary Search Tree라는 이름에서 알 수 있듯이, BST는 일종의 Binary Tree 입니다. (부모가 2개 이하의 자식을 갖는 트리)

그리고 Binary Tree 중에 특정 조건을 만족하는 경우에 검색에 이점이 생기기 때문에, 이들을 따로 BST로 분류를 합니다.

 

 

 

 

 

2.  성립조건

성립 조건은 생각보다 간단합니다. 

'부모를 기준으로 부모 보다 작은 값은 왼편에, 부모 보다 큰 값은 오른편에 위치한다.'를 만족하면 됩니다.

(당연히 이진 트리라는 조건도 만족해야합니다.)

글로 보는 것 보다 그림으로 보면 쉽게 이해할 수 있습니다.

 

 

각 노드를 기준으로 작은 수는 왼쪽에, 큰 수는 오른쪽에 위치하고 있는 것을 확인할 수 있습니다.

 

 

 

 

3.  이점

성립 조건에서 언급한 특성 덕분에 일반적인 상황에서 검색, 삽입, 삭제가 O(logN)의 시간복잡도로 해결이 됩니다.

찾아야하는 범위를 계속 반씩 줄여나가기 때문에 최대 트리의 높이만큼 확인을 하면 원하는 대상을 찾을 수 있습니다.

 

 

 

 

4.  약점

위에서 일반적인 상황을 언급했습니다. 그렇다면 일반적이지 않은 상황도 있겠지요?

일반적이지 않은 최악의 경우에는 모든 연산에서 O(n)의 시간복잡도가 필요하게 됩니다.

어떤 상황이 일반적이지 않은지 그림으로 살펴보겠습니다.

 

트리가 위의 이미지처럼 한쪽으로 치우치는 경우에는 기대했던 성능을 보여주지 못하게 됩니다.

 

 

 

 

5.  보완

이런 경우가 생길 가능성이 있는 자료구조를 쓰는 것은 위험합니다. 그래서 BST의 이러한 단점을 보완하고자 만들어진 자료구조가 Self Balancing Tree이고 대표적으로 AVL Tree, Red-Black-Tree 등이 있습니다.

이들은 스스로 치우치지 않도록 밸런싱을 하기 때문에 모든 경우에서 O(logN)의 성능을 보여줍니다.

 

 

 

 

6. 구현

이론만 하기보다 구현을 직접해보는 것이 기억에 더 오래 가지 않을까요?

저는 자바스크립트로 구현을 해보았습니다.

 

삭제를 구현하다보니 역시 구현해보길 잘했다는 생각이 들었습니다.

삭제는 3가지 경우를 핸들링해주어야 합니다.

 

1) 자식이 없는 경우

 => 삭제하려는 노드를 삭제한다. 끝

 

2) 자식이 한쪽에 있는 경우

=> 삭제하려는 노드를 삭제하고 자식을 그 자리로 옮겨준다. 끝

 

3) 자식이 양쪽인 경우

=> 삭제하려는 노드를 삭제한다.

=> 삭제하려는 노드의 왼쪽의 최대 노드 혹은 오른쪽의 최소 노드를 그 자리로 옮겨준다.

 

자식이 양쪽인 경우에는 조금 더 복잡한 과정이 필요합니다. ( 이런 방법은 누가 처음에 생각해냈는지 대단한 것 같습니다 ㅎㅎ )

 

구현 보기 

class Node {
  value;
  parent;
  left;
  right;

  constructor(num, node) {
    this.value = num;
    this.parent = node;
  }
}

class BST {
  root;

  add(number) {
    if (this.root == undefined) {
      this.root = new Node(number);
      return;
    } else {
      this.iterateForAdd(this.root, number);
    }
  }

  iterateForAdd(node, value) {
    if (node.value >= value) {
      if (node.left) {
        this.iterateForAdd(node.left, value);
        return;
      } else {
        node.left = new Node(value, node);
        return;
      }
    }

    if (node.value < value) {
      if (node.right) {
        this.iterateForAdd(node.right, value);
        return;
      } else {
        node.right = new Node(value, node);
        return;
      }
    }
  }

  find(value) {
    return this.iterateForFind(this.root, value);
  }

  iterateForFind(node, value) {
    if (node.value === value) {
      return node;
    }

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

  delete(value) {
    this.root = this.deleteNode(this.root, value);
  }

  deleteNode(node, value) {
    if (!node) {
      return null;
    }
    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
    } else {
      if (!node.left && !node.right) {
        return null;
      }
      if (!node.left) {
        return node.right;
      }
      if (!node.right) {
        return node.left;
      }

      node.value = this.findMinNode(node.right).value;
      node.right = this.deleteNode(node.right, node.value);
    }
    return node;
  }

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

 

 

 

7. Binary Search 랑 유사하지 않나?

BST를 보면서 Binary Search가 계속 떠오르지 않으셨나요?

둘은 비슷한듯 하지만 다른 부분이 있습니다.

 

기본적으로 검색 범위를 반으로 줄여나가는 동일한 방법을 사용하고 있습니다. 따라서 O(logN) 의 검색 성능을 보여줍니다.

하지만 Binary Search는 '정렬 된 배열' 위에서 작동하는 방법이기 때문에 삽입, 삭제에서 차이가 발생합니다.

새로운 요소를 추가하거나 삭제할 때 추가적인 정렬비용이 발생하기 때문에 O(logN) 으로 삽입, 삭제가 가능한 BST가 보다 나은 효율을 보여줍니다!

 

 

 

 

 

 

---