No Silver Bullet

이진검색트리(Binary Search Tree)

search tree binary search tree

자료 집합에서 이분 검색을 수행할 수 있게 하려면 자료들이 정렬되어 있어야 한다. 매번 정렬을 한 후 이분 검색을 할 수는 없기 때문에 자료의 삽입, 삭제 작업 이후에도 자료가 정렬되어 있도록 유지해야 한다. 배열에서 이분 검색은 \(O(log_2n)\)에 수행되지만 원소의 삭제, 삽입 과정은 자료를 정렬되게 유지하게 위해 평균 \(n/2\)개의 자료를 밀거나 당기는 작업이 필요하여 \(O(n)\)의 수행 시간을 갖는다. 따라서 이분 검색은 삽입, 삭제가 정적인 자료 구조에 적합한 방식이다. 만약 자료의 삽입, 삭제가 빈번하게 이루어지는 경우 이진 트리 검색을 사용하는 것이 좋다.

이진 검색 트리(Binary Search Tree)

이진 트리 검색은 동적인 자료 구조인 이진 검색 트리(Binary Search Tree, 이하 BST)를 이용하여 자료를 검색한다. 이진 검색 트리는 다음과 같은 속성을 유지하는 트리다.

  • 각 노드의 키(key) 값은 유일하다.
  • 키 값들의 순서가 존재한다.
  • 각 노드는 왼쪽, 오른쪽 두 자식 노드를 갖는다.
  • 노드의 왼쪽 자식 노드를 루트로 하는 서브 트리에는 그 노드의 값보다 작은 값들을 갖는 노드들로 이루어져 있다.
  • 노드의 오른쪽 자식 노드를 루트로 하는 서브 트리에는 그 노드의 값보다 큰 값들을 갖는 노드들로 이루어져 있다.

이진 트리는 그 구조상 이분 검색과 거의 유사하게 자료를 찾기 때문에 검색 속도가 매우 빠르다. 트리의 높이를 \(h\)라고 했을 때 \(O(h)\)의 시간복잡도를 갖는다. 트리가 균형 잡혀 있다면 \(h=log_2n\)이므로 \(O(log_2n)\)의 검색 시간을 갖는다. 이진 검색 트리에서의 검색은 다음과 같이 이루어진다.

1. 키값이 현재 노드의 값과 같으면 현재 노드를 반환한다(만약 현재 노드가 없다면(NULL), 해당 키 값은 존재하지 않는다).
2. 키값이 현재 노드의 값보다 작으면 왼쪽 서브 트리에서 재귀적으로 검색한다.
3. 키값이 현재 노드의 값보다 크면 오른쪽 서브 트리에서 재귀적으로 검색한다.

이진 검색 트리에 새로운 자료를 삽입하는 과정은 검색 과정과 유사하다. 이진 검색 트리의 루트 노드부터 삽입할 노드의 키 값과 비교하면서 삽입할 위치를 찾다보면 말단 노드에 이르게 된다. 말단 노드와 키 값을 비교하여 말단 노드의 왼쪽 또는 오른쪽에 삽입하면 된다. (시간복잡도는 \(O(h)\))

이진 검색 트리에서의 삭제 작업은 검색을 통하여 삭제할 노드를 찾는 것부터 시작한다. 삭제할 노드를 찾고나면 삭제할 노드의 자식 수에 따라 다음 세 가지 경우로 나누어진다. (시간복잡도는 \(O(h)\))

  • 자식 노드가 없는 경우: 해당 노드를 삭제한 후, 부모 노드와의 연을 끊으면 된다.
  • 자식 노드가 1개인 경우: 해당 노드를 삭제하고, 그 위치에 자식 노드를 세우면 된다.
  • 자식 노드가 2개인 경우: 해당 노드의 노드를 삭제하고, 그 위치에 해당 노드의 왼쪽 서브 트리에서 가장 큰 노드 또는 오른쪽 서브 트리에서 가장 작은 노드를 떼어다가 놓으면 된다.

균형잡힌 검색 트리(Balanced Search Tree)

이진 검색 트리의 단점은 자료의 입력 순서에 따라 트리의 높이 \(h\)가 달라진다는 것이다. 검색, 삽입, 삭제 연산 모두 \(h\)에 의해 수행 속도가 영향을 받기 때문에 트리의 높이를 낮게 만드는 것이 중요하다. 트리의 높이가 낮으려면 트리의 모양이 균형이 잡혀있어야 한다. 때문에 삽입, 삭제 과정에서 트리가 균형 잡히도록 하는 많은 연구가 진행되었고, 균형 잡힌 트리로 알려진 대표적인 자료 구조들로는 AVL tree, Red-black tree, Splay tree, Treap 등이 있다.

C++ STL에서는 std::set, set::map, set::multiest, set::multimap등의 균형잡힌 검색 트리(Red-black tree로 구현되었다고 한다)를 제공한다. 이러한 라이브러리를 이용하여 검색, 삽입, 삭제 과정을 모두 \(O(log_2n)\)에 수행할 수 있다. 다만, 위 라이브러리들은 기초적인 연산(검색, 삽입, 삭제)만 제공하므로 \(k\)번째 원소를 찾는 것과 같이 좀 더 추가적인 연산을 필요로 한다면 직접 균형잡힌 검색 트리를 구현해야 한다. AVL tree나 Red-black tree의 경우 다소 복잡하기 때문에 시간이 촉박한 프로그래밍 대회에서 구현하기에는 부적합하고 대신 그보다 비교적 간결한 Splay tree나 Treap을 구현하여 사용하는 것이 좋다.

Treap

추가 예정

Splay Tree

추가 예정

Related Posts