BST 균형트리 (AVL, RB, 자료구조)
이진 트리 위에 "왼쪽은 작은 값, 오른쪽은 큰 값"이라는 단 한 줄의 정렬 규칙을 얹으면 곧바로 이진 탐색 트리(BST)가 된다. 이 한 규칙 덕분에 평균 O(log n) 시간에 탐색·삽입·삭제가 가능해지며, 자료구조 학습에서 처음 만나는 진짜 "실용적인" 트리이기도 하다. 다만 BST에는 결정적인 약점이 있는데, 데이터가 정렬된 순서로 들어오면 한쪽으로 편향되어 O(n)으로 떨어진다는 점이다. 이 약점을 해결하기 위해 등장한 것이 균형 트리(Balanced Tree)이며, 대표적으로 AVL 트리와 Red-Black(RB) 트리가 있다. 본 글은 BST의 정의·연산·시간복잡도부터 두 균형 트리의 차이까지 세심하게 정리한다(출처: 위키백과 — Binary Search Tree). 제가 학교 알고리즘 과제에서 정렬된 데이터로 BST를 만들었다가 검색 시간이 선형으로 늘어나는 모습을 직접 본 후로는 "BST는 좋지만 균형 보장이 없으면 보험이 부족하다"는 사실을 손끝으로 받아들였고, 그 후로 표준 라이브러리의 정렬 컨테이너가 거의 모두 RB 트리 위에 서 있다는 사실이 비로소 이해되었다.
BST의 정의와 기본 연산
이진 탐색 트리(Binary Search Tree, BST)는 다음 두 가지 조건을 만족하는 이진 트리이다. 첫째, 한 노드의 왼쪽 서브트리의 모든 키가 그 노드의 키보다 작다. 둘째, 오른쪽 서브트리의 모든 키가 그 노드의 키보다 크다. 이 두 조건이 모든 서브트리에 재귀적으로 적용되며, 그 결과 BST의 중위 순회 결과는 항상 오름차순 정렬이 보장된다는 핵심 성질이 만들어진다.
BST의 세 가지 핵심 연산은 탐색·삽입·삭제이며, 모두 같은 패턴을 공유한다. "찾을 키와 현재 노드의 키를 비교해 왼쪽 또는 오른쪽으로 한 단계씩 내려간다"는 한 줄로 압축된다. 다음은 노드 기반 BST의 파이썬 구현이다.
class Node:
__slots__ = ("k", "left", "right")
def __init__(self, k):
self.k = k; self.left = None; self.right = None
def search(n, k): # 탐색
if n is None or n.k == k: return n
return search(n.left, k) if k < n.k else search(n.right, k)
def insert(n, k): # 삽입
if n is None: return Node(k)
if k < n.k: n.left = insert(n.left, k)
elif k > n.k: n.right = insert(n.right, k)
return n
def min_node(n):
while n.left: n = n.left
return n
def delete(n, k): # 삭제
if n is None: return None
if k < n.k: n.left = delete(n.left, k)
elif k > n.k: n.right = delete(n.right, k)
else:
if n.left is None: return n.right
if n.right is None: return n.left
succ = min_node(n.right) # 오른쪽 서브트리의 최솟값으로 교체
n.k = succ.k
n.right = delete(n.right, succ.k)
return n삭제 연산이 가장 까다로운데, 자식이 0개·1개·2개인 세 경우를 나누어 처리해야 한다. 핵심은 자식이 2개인 경우 "오른쪽 서브트리의 최솟값(또는 왼쪽 서브트리의 최댓값)으로 자기 자신을 교체한 뒤, 그 후계 노드를 다시 삭제"하는 패턴이다. 여기서 후계 노드(successor)란 중위 순회 결과에서 그 노드 바로 다음에 오는 노드를 의미하며, BST에서는 오른쪽 서브트리의 최솟값이 항상 후계 노드가 된다.
BST의 시간복잡도는 트리의 높이 h에 정확히 비례한다.
| 연산 | 평균(균형 시) | 최악(편향 시) |
|---|---|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
평균 O(log n)은 매력적이지만, 편향 시 O(n)이라는 최악의 비용이 BST의 결정적 약점이다. 만약 정렬된 데이터(예: 1, 2, 3, …, n)를 차례로 삽입하면 트리는 사실상 오른쪽으로만 자라는 연결리스트가 되어 모든 연산이 O(n)으로 떨어진다. 솔직히 제 경험상 학교 과제에서 가장 자주 놓치는 사고가 정확히 이 시나리오였고, 입력 데이터를 셔플(shuffle)하면 모든 게 정상 동작하다가 정렬된 데이터에서 시간 초과가 떨어지는 모습을 처음 봤을 때 균형 보장의 가치를 비로소 체감했다.
균형 트리 — AVL 트리
AVL 트리(AVL Tree)는 1962년 아델손-벨스키(Adelson-Velsky)와 란디스(Landis)가 발표한 최초의 자기 균형 이진 탐색 트리이다(출처: 위키백과 — AVL Tree). AVL의 핵심 규칙은 단 하나로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하여야 한다는 것이다. 이 높이 차를 균형 인수(Balance Factor)라 부르며, BF = (왼쪽 높이) − (오른쪽 높이)가 −1, 0, +1 중 하나여야 AVL 조건을 만족한다.
삽입 또는 삭제 후 한 노드의 BF가 ±2가 되면 그 즉시 트리를 회전(rotation)시켜 균형을 복원한다. 회전에는 네 가지 패턴이 있으며, 시험에서 자주 출제되는 항목이다.
| 불균형 패턴 | 회전 종류 | 설명 |
|---|---|---|
| LL (왼쪽-왼쪽) | 단일 우회전 | 왼쪽 자식의 왼쪽이 무거움 → 오른쪽으로 한 번 회전 |
| RR (오른쪽-오른쪽) | 단일 좌회전 | 오른쪽 자식의 오른쪽이 무거움 → 왼쪽으로 한 번 회전 |
| LR (왼쪽-오른쪽) | 좌-우 이중 회전 | 왼쪽 자식을 좌회전 후 다시 우회전 |
| RL (오른쪽-왼쪽) | 우-좌 이중 회전 | 오른쪽 자식을 우회전 후 다시 좌회전 |
여기서 회전이란 부모-자식 관계를 한 단계 비틀어 트리의 모양을 바꾸되 중위 순회 결과(즉 정렬 순서)는 유지하는 국소 연산을 의미한다. 회전은 모두 O(1) 시간에 끝나며, AVL은 한 번의 삽입·삭제 후 최대 O(log n)번의 회전만으로 균형을 복원한다.
AVL의 시간복잡도는 다음과 같다.
| 연산 | 시간복잡도 |
|---|---|
| 탐색 | O(log n) — 항상 |
| 삽입 | O(log n) |
| 삭제 | O(log n) |
| 회전 | O(1) (1~2회) |
AVL은 균형이 매우 엄격하기 때문에 탐색 성능이 가장 좋은 균형 트리이다. 다만 삽입·삭제 후 균형을 더 자주 복원해야 하므로 RB 트리에 비해 쓰기 성능이 약간 떨어진다. 그래서 실무에서는 "읽기 비중이 높으면 AVL, 쓰기 비중이 높으면 RB"라는 단순한 선택 규칙이 자주 쓰인다.
균형 트리 — Red-Black 트리
Red-Black 트리(RB Tree)는 1972년 루돌프 바이어(Rudolf Bayer)가 처음 제안하고 1978년 LLeen과 Tarjan이 다듬어 표준화한 자기 균형 이진 탐색 트리이다(출처: 위키백과 — Red–Black Tree). 각 노드에 빨강 또는 검정의 색을 부여하고, 다섯 가지 색 규칙을 통해 트리의 균형을 느슨하게(loosely balanced) 유지한다. AVL보다 균형이 덜 엄격하지만, 그 대신 삽입·삭제 후 재조정 비용이 평균적으로 적어 실무에서 가장 널리 사용되는 균형 트리가 되었다.
RB 트리의 다섯 가지 색 규칙은 다음과 같다.
- 모든 노드는 빨강 또는 검정 중 하나의 색을 가진다.
- 루트 노드는 항상 검정이다.
- 모든 잎(NIL)은 검정이다. (NIL은 가상의 외부 노드)
- 빨강 노드의 자식은 항상 검정이다. (빨강-빨강 금지)
- 루트에서 임의의 잎까지 가는 경로의 검정 노드 수가 모두 같다. (검정 높이 동일)
여기서 검정 높이(black-height)란 한 노드에서 잎까지의 경로에 포함된 검정 노드의 수를 의미하며, 위 다섯 규칙의 마지막 조건이 균형의 핵심 메커니즘이다. 이 다섯 규칙을 모두 만족하면 트리의 최대 높이가 2·log(n+1) 이내로 보장되며, 따라서 모든 연산이 O(log n) 시간에 끝난다.
삽입·삭제 후 규칙이 깨지면 RB 트리는 회전(rotation)과 재색칠(recoloring) 두 가지 도구로 복원한다. AVL이 균형 인수를 보고 회전하는 것과 달리, RB는 부모·삼촌·조부모의 색을 보고 케이스를 나누어 처리한다. 복잡해 보이지만 평균적으로 회전 0~2회·재색칠 O(log n)회로 균형이 회복되며, 이 가벼움이 RB의 가장 큰 강점이다.
| 비교 항목 | AVL 트리 | Red-Black 트리 |
|---|---|---|
| 균형 기준 | 높이 차 ≤ 1 (엄격) | 색 규칙 (느슨) |
| 최대 높이 | 약 1.44·log n | 약 2·log n |
| 탐색 성능 | 더 빠름 | 약간 느림 |
| 삽입·삭제 후 재조정 | 자주, 비교적 무거움 | 드물게, 가벼움 |
| 적합한 상황 | 읽기 위주 | 쓰기 빈번 / 표준 라이브러리 |
| 실무 채택 | DB 일부, AVL Tree 직접 구현 | Java TreeMap, C++ std::map, Linux 커널의 CFS 스케줄러, epoll 등 |
실무에서 가장 자주 마주치는 균형 트리가 사실상 RB 트리라는 점이 인상적이다. C++의 std::map·std::set, 자바의 TreeMap·TreeSet, 리눅스 커널의 CFS(Completely Fair Scheduler), epoll의 대기 이벤트 관리가 모두 RB 트리 위에 서 있다. 솔직히 이건 예상 밖이었는데, 제가 학교 수업에서 처음 RB 트리를 봤을 때는 다섯 규칙이 너무 인위적으로 보였지만, 그 다섯 규칙 덕분에 회전 횟수가 평균적으로 줄어든다는 분석을 직접 보고 나서야 "엄격한 균형보다 느슨한 균형이 실무에서 더 빠를 수 있다"는 사실을 받아들였다.
마지막으로 시험에서 자주 쓰이는 한 줄 요약을 정리하면, "BST는 평균 O(log n)이지만 편향 시 O(n)으로 떨어지며, 이를 보장하기 위한 자기 균형 트리가 AVL(엄격·읽기 우선)과 Red-Black(느슨·쓰기 빈번 + 실무 표준)이다"라는 두 문장이 표준 답안 표현으로 통한다. 다음 글에서는 같은 트리 구조 위에 부모가 자식보다 항상 크다(또는 작다)는 다른 규칙을 얹은 힙(Heap)과 우선순위 큐를 이어 다룬다.
메타 디스크립션: 이진 탐색 트리(BST)의 정의·연산·시간복잡도부터 AVL 트리의 균형 인수와 4가지 회전, Red-Black 트리의 5가지 색 규칙과 실무 채택 사례까지 자료구조 입문자 관점에서 세심하게 정리합니다.