Height-Balanced BST

트리에서의 용어

• 노드의 깊이: 루트 노드에서부터의 간선의 갯수
• 노드의 높이: leaf 노드까지의 간선의 최대 갯수
• 트리의 높이: 루트 노드의 높이

정의

임의의 항목 삽입/삭제에 대해 자동으로 높이를 작게 유지하는 BST.
N개의 노드를 가진 균형 BST의 높이는 항상 logN 이다. 또한, 각 노드의 두 서브트리의 높이 차이는 1을 넘지 않는다.

참고: Height-Balanced BST 의 높이가 logN인 이유 높이 h의 트리의 최대 노드 갯수 N은 "2^(h+1) - 1". 다시 말해, "N <= 2^(h+1) - 1" 이는 "h >= (log2N)"

특징

BST 에의 연산(검색/삽입/삭제)에서 가장 중요한 것은 트리의 높이다. (N개 노드를 가진 BST의 탐색 연산의 시간복잡도는 O(logN) 에서 O(N)까지 다양하다.)
높이 균형 BST는 검색, 삽입, 삭제 연산을 모두 O(logN)의 시간 복잡도로 수행할 수 있다. 높이 균형 BST는 성능 향상에 강점이 있다.

Height-Balanced BST 구현은 이진 탐색 특성과 높이 균형 특성을 충족해야 한다. 널리 사용되는 Height-Balanced BST 는 다음과 같다.

• Red-black tree
• AVL tree
• Splay tree
• Treap

활용 사례

가장 심층적인 활용 사례는 집합/맵이다.
집합에서 트리 집합(Java 에서 TreeSet)과 해시 집합(Java 에서 HashSet) 모두 Height-Balanced BST 를 사용한다. 트리 집합의 경우 해시 집합과 다르게 집합의 키가 정렬되어 있다. 해시 집합은 해시 알고리즘으로 구현되지만, 동일한 해시 키를 가진 요소가 많을 경우 검색의 시간 복잡도를 O(N)에서 O(logN)으로 향상시키기 위해 Height-Balanced BST 를 사용한다.