데이터를 효율적으로 저장하고 탐색하기 위해 다양한 검색 트리(Search Tree)가 사용됩니다. 각 트리는 자체 균형 방식과 구조적 특징이 달라서, 상황에 따라 성능 차이가 크게 벌어집니다. 이 글에서는 대표적인 검색 트리들의 특징을 살펴보고, 삽입·삭제·탐색 연산의 시간 복잡도를 평균 경우와 최악의 경우로 나누어 비교해 보겠습니다.
대표적인 검색 트리의 종류
가장 기본이 되는 검색 트리는 이진 탐색 트리(Binary Search Tree, BST)입니다. BST는 왼쪽 자식에는 작은 값, 오른쪽 자식에는 큰 값을 배치하는 단순한 규칙으로 동작하지만, 데이터가 정렬된 순서로 삽입되면 트리가 한쪽으로 기울어져 성능이 크게 저하될 수 있습니다.
이러한 한계를 보완하기 위해 여러 가지 개선된 트리 구조가 등장했습니다.
- AVL 트리: 모든 노드에서 좌우 서브트리의 높이 차이를 1 이하로 유지하는 엄격한 자기 균형 트리입니다.
- B 트리: 하나의 노드에 여러 키를 저장할 수 있는 다원(多元) 균형 트리로, 디스크 기반 데이터베이스와 파일 시스템에 널리 활용됩니다.
- 레드-블랙 트리(Red-Black Tree): 노드에 색상 속성을 부여해 균형을 유지하며, C++ STL의 map/set 등 표준 라이브러리에서 사용됩니다.
- 스플레이 트리(Splay Tree): 최근 접근한 노드를 루트로 끌어올리는 방식으로 동작하며, 반복 접근 패턴에서 뛰어난 성능을 보입니다.
평균 경우(Average Case) 시간 복잡도 비교
아래 표는 각 검색 트리에서 삽입, 삭제, 탐색 연산이 수행될 때의 평균 시간 복잡도를 정리한 것입니다.
| 검색 트리 | 평균 경우 | ||
|---|---|---|---|
| 삽입 | 삭제 | 탐색 | |
| 이진 탐색 트리(BST) | O(log n) | O(log n) | O(log n) |
| AVL 트리 | O(log2 n) | O(log2 n) | O(log2 n) |
| B 트리 | O(log n) | O(log n) | O(log n) |
| 레드-블랙 트리 | O(log n) | O(log n) | O(log n) |
| 스플레이 트리 | O(log2 n) | O(log2 n) | O(log2 n) |
평균적인 상황에서는 모든 트리가 로그 시간 안에 연산을 처리합니다. 특히 자기 균형 트리인 AVL, B, 레드-블랙, 스플레이 트리는 데이터 분포와 무관하게 일관된 로그 시간 성능을 보장합니다.
최악의 경우(Worst Case) 시간 복잡도 비교
최악의 경우에서야 진짜 차이가 드러납니다. 아래 표를 확인해 보세요.
| 검색 트리 | 최악의 경우 | ||
|---|---|---|---|
| 삽입 | 삭제 | 탐색 | |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) |
| AVL 트리 | O(log2 n) | O(log2 n) | O(log2 n) |
| B 트리 | O(log n) | O(log n) | O(log n) |
| 레드-블랙 트리 | O(log n) | O(log n) | O(log n) |
| 스플레이 트리 | O(log2 n) | O(log2 n) | O(log2 n) |
핵심 요약
일반 BST는 최악의 경우 트리가 사실상 연결 리스트처럼 변형되어 모든 연산이 O(n)까지 느려질 수 있습니다. 반면 AVL 트리, B 트리, 레드-블랙 트리, 스플레이 트리는 회전이나 재구성 같은 균형 유지 메커니즘 덕분에 최악의 경우에도 O(log n)의 성능을 보장합니다.
따라서 예측 가능한 성능이 중요한 실무 환경에서는 단순 BST보다 자기 균형 트리를 선택하는 것이 바람직하며, 데이터베이스나 파일 시스템처럼 대용량 블록 단위 입출력이 많은 환경에서는 B 트리 계열이 특히 유리합니다.