균형 이진 탐색 트리란 무엇인가?
이번 글에서는 균형 이진 탐색 트리(Balanced Binary Search Tree)에 대해 알아보겠습니다. 이진 탐색 트리(Binary Search Tree, BST)는 각 노드의 왼쪽 자식에는 더 작은 값이, 오른쪽 자식에는 더 큰 값이 위치하는 이진 트리입니다.
BST에서 원소를 탐색할 때의 평균 시간 복잡도는 O(log n)입니다. 이는 트리의 높이(height)에 의해 결정되는데, 문제는 BST의 속성을 유지하는 과정에서 트리가 한쪽으로 치우친 편향(skewed) 트리가 될 수 있다는 점입니다.
편향 트리의 문제점
트리가 한쪽으로 기울어지면 다음과 같은 형태가 됩니다.
위 그림은 엄연히 트리이지만, 실제로는 연결 리스트(linked list)와 거의 같은 모습입니다. 이런 형태의 트리에서 원소를 탐색하려면 최악의 경우 모든 노드를 순회해야 하므로 시간 복잡도가 O(n)까지 증가합니다. 이는 이진 트리의 장점을 전혀 살리지 못하는 비효율적인 상황입니다.
높이 균형 트리로 해결하기
이러한 문제를 해결하기 위해 높이 균형(height-balanced) 트리를 사용할 수 있습니다. 트리가 편향되지 않도록 강제로 균형을 유지하는 것인데, 핵심 아이디어는 다음과 같습니다.
- 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 최소한으로 유지한다.
- 삽입·삭제 연산 시 필요하면 회전(rotation) 등의 방법으로 트리의 균형을 재조정한다.
이렇게 하면 트리의 높이가 log n 수준으로 유지되어, 탐색·삽입·삭제 연산을 모두 O(log n) 시간 안에 처리할 수 있습니다.
대표적인 균형 이진 탐색 트리 기법
트리의 균형을 유지하는 방법은 여러 가지가 있으며, 대표적인 기법은 다음과 같습니다.
- AVL 트리 — 두 자식 서브트리의 높이 차이가 1 이하가 되도록 엄격하게 균형을 유지하는 트리
- 레드-블랙 트리(Red-Black Tree) — 노드에 색상 속성을 부여해 균형을 관리하며, 삽입·삭제 시 재조정 비용이 상대적으로 적은 트리
균형 잡힌 트리의 형태
앞서 살펴본 편향된 트리를 높이 균형 형태로 변환하면 다음과 같은 모습이 됩니다.
같은 데이터를 담고 있지만, 트리의 높이가 크게 줄어들어 탐색 성능이 O(log n)으로 개선됩니다. 실무에서는 C++의 std::map, Java의 TreeMap 등 많은 표준 라이브러리가 레드-블랙 트리를 기반으로 구현되어 있으니 참고하면 좋습니다.