레드블랙트리: 최악 높이를 제어하는 균형 이진검색트리
레드블랙트리의 색상 불변식, 높이 상한, 회전 기반 복구 과정과 BST·AVL 비교, 인메모리 인덱스 활용을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
편향된 BST가 감당하지 못하는 높이 문제
이진검색트리(BST)는 연산 시간이 트리 높이에 따라 달라진다. 삽입 순서가 한쪽으로 쏠리면 트리가 선형 구조에 가까워지고, 최악의 경우 탐색 비용은 O(n)이 된다.
레드블랙트리(Red-Black Tree)는 노드 색상과 회전을 이용해 이 문제를 제어한다. 평균뿐 아니라 최악의 경우에도 높이를 O(log n)으로 제한하므로, 표준 라이브러리와 커널 자료구조에서 널리 쓰이는 균형 이진검색트리다.
각 노드는 Red 또는 Black 색을 가지며 다음 불변식을 지켜 균형을 유지한다.
- 루트는 Black이다.
- 모든 리프(NIL)는 Black이다.
- Red 노드의 자식은 모두 Black이다.
- 임의의 노드에서 리프까지 가는 모든 경로는 같은 수의 Black 노드, 즉 black-height를 가진다.
이 제약으로 트리 높이는 h ≤ 2·log2(n+1)을 만족한다. 단순 BST의 최악 O(n)과 달리 레드블랙트리의 탐색·삽입·삭제는 O(log n)으로 유지된다.
재색칠과 회전으로 불변식을 복구한다
새 노드는 Red로 삽입한다. 이후 부모도 Red라면 불변식이 깨질 수 있으므로, 삼촌 노드의 색과 노드 배치에 따라 재색칠 또는 좌·우 회전을 수행한다. 마지막에는 루트를 Black으로 보장한다.
삭제에서는 Black 노드가 제거될 때 black-height가 달라질 수 있다. 이때 double black을 해소하기 위해 형제 노드와 그 자식의 색을 기준으로 재색칠과 회전을 적용한다.
삽입은 최대 2회 회전하고, 삭제는 최대 3회 회전 및 O(log n) 단계의 재색을 수행한다. 회전 자체는 O(1) 국소 변환이다.
NIL 센티널을 두면 null 분기를 줄일 수 있고, 루트 Black 규칙도 일관되게 다룰 수 있다. 중복 키는 거부, 갱신, 다중값 중 어떤 정책을 쓸지 구현 전에 정해야 한다.
높이 제어와 구현 시 고려할 점
black-height 불변식은 순차 키 삽입처럼 BST를 선형화시키는 입력에서도 편향 성장을 억제한다. 노드별 오버헤드는 색상 1비트와 NIL 센티널 정도이며, 포인터 기반 트리와 함께 구현하기 쉽다.
AVL과 비교하면 구현은 다소 복잡하지만 업데이트 지연이 짧고 회전 횟수가 적은 경향이 있다. 동시성 요구가 낮다면 coarse-grained RW락으로 운영할 수 있다. 더 높은 성능이 필요하면 노드 단위 락-커플링이나 RCU 기반 읽기 병렬화를 적용할 수 있다.
| 지표 | 단순 BST | 레드블랙트리 | AVL |
|---|---|---|---|
| 성능(최악 탐색) | O(n) | O(log n) | O(log n) |
| 업데이트 비용 | 낮음(불균형 방치) | 낮음 |
중간(회전/재균형 빈번) |
| 일관성(지터) | 입력 패턴에 민감 | 안정 지연 특성 | 매우 안정 지연 |
| 확장성(동시성) | 쉬움(락 단순) | 쉬움(국소 회전) | 보통(재균형 빈도 영향) |
| 안정성(최악 케이스) | 취약 | 강함 | 강함 |
| 운영 편의 | 구현 단순 | 표준 구현 다수, 검증 용이 | 구현 복잡 |
정렬된 키 집합이 필요한 곳
C++의 std::map·std::set, Java의 TreeMap·TreeSet은 레드블랙트리를 내부 구현에 채택한다. 키 정렬 상태를 유지하면서 범위 질의(range query)를 지원해야 할 때 적합하다.
Linux Completely Fair Scheduler(CFS), 메모리 할당자(VMA 트리), 네트워크 라우팅 캐시처럼 안정적인 지연 특성이 필요한 시스템 자료구조에도 쓰인다. 중소 규모 인메모리 인덱스나 LRU·만료 큐의 키 기반 정렬 관리에도 적용할 수 있다.
반면 대용량 디스크 인덱스는 B-Tree나 B+Tree가 더 선호된다. 레드블랙트리는 메모리 중심 구조에서 선택하기 좋다.
수치로 보는 최악 경로
높이 상한은 h ≤ 2·log2(n+1)이다. n=1,000,000이면 log2(n+1)≈19.93이고, 높이는 h≤≈39.9가 된다. 최악 탐색에서 단순 BST의 O(n)=1,000,000과 비교하면 레드블랙트리는 O(log n)≈40 수준이다.
삽입과 삭제에서 회전 횟수가 상수로 제한되므로 높은 처리량을 확보할 수 있다. 입력 분포에 덜 흔들리는 응답시간, 검증된 표준 구현의 재사용성, 유지보수 편의성도 함께 얻는다.