왜 RBT가 필요한가?
- 일반 BST는 입력 순서에 따라 편향되어
O(N)까지 느려질 수 있습니다. - RBT는 "완전 균형"은 아니지만, 규칙으로 높이를 충분히 작게 제한해
O(log N)을 보장합니다. - 핵심은 회전(rotation) + 색 변경(recoloring)으로 삽입/삭제 후 균형을 복구하는 것입니다.
레드-블랙 트리 5가지 규칙
- 모든 노드는 Red 또는 Black이다.
- 루트는 Black이다.
- 모든 리프(NIL, null sentinel)는 Black이다.
- Red 노드의 자식은 모두 Black이다. (연속 Red 금지)
- 어떤 노드에서 내려가는 모든 경로는 동일한 수의 Black 노드를 가진다. (Black Height 동일)
규칙 시각화
규칙 4 (레드 연속 금지):
[B]
/ \
[R] [R]
/ \ / \
[B][B][B][B] (OK)
규칙 5 (블랙 높이 동일):
[B]
/ \
[B] [B]
/ \
[R] [R]
\ /
[NIL] [NIL]
모든 루트->NIL 경로의 Black 개수 동일회전(Rotation) 직관
회전은 BST의 중위 순서(정렬 순서)를 깨지 않으면서 트리 모양만 바꿉니다.
왼쪽 회전(Left Rotate) 오른쪽 회전(Right Rotate)
x y
/ \ / \
T1 y -----> x T3
/ \ / \
T2 T3 T1 T2
(x의 오른쪽이 위로) (y의 왼쪽이 위로)- 회전만으로는 부족할 수 있어, 보통 색 변경과 함께 수행합니다.
삽입 시 복구(Insert Fix-up) 핵심 흐름
새 노드는 Red로 삽입합니다. (처음부터 Black이면 Black Height 규칙 깨지기 쉬움)
부모가 Black이면 종료
- 규칙 위반 없음 -> 추가 작업 불필요
부모가 Red이면 위반 발생 (Red-Red)
삼촌(uncle) 색에 따라 처리:
- 삼촌이 Red:
- 부모/삼촌을 Black, 조부모를 Red로 recolor
- 기준 노드를 조부모로 올려 반복 검사
- 삼촌이 Black(NIL 포함):
- LL / RR / LR / RL 형태에 맞춰 회전
- 회전 후 부모/조부모 색 조정
마무리: 루트는 항상 Black으로 보정
삭제 시 복구(Delete Fix-up) 핵심 흐름
- Red 노드를 지우는 경우는 비교적 단순합니다.
- 문제는 Black 노드 삭제로, 경로의 Black 개수가 부족해질 수 있습니다.
- 이를 개념적으로 "더블 블랙(double black)" 상태로 보고 복구합니다.
복구 판단 기준:
- 형제(sibling) 색
- 형제의 자식 색 조합
- 부모 색
처리 방식:
- recolor만으로 해결되는 경우
- 회전 + recolor가 필요한 경우
삭제 복구는 삽입보다 케이스가 많아 구현 난도가 높습니다.
복잡도와 보장
- 탐색/삽입/삭제:
O(log N) - 이유: RBT는 높이
h가2 * log2(N + 1)이하가 되도록 제한됩니다. - 즉, 최악 케이스에서도 선형으로 무너지지 않도록 설계되어 있습니다.
STL과의 관계
std::map,std::set,std::multimap,std::multiset은
대부분 구현체에서 레드-블랙 트리를 기반으로 동작합니다.- 그래서 정렬 상태를 유지하면서 연산 복잡도
O(log N)을 제공합니다.
학습 전략 + 체크 질문
- RBT를 직접 구현하기보다, "왜 균형이 유지되는가"를 먼저 이해하는 것이 효율적입니다.
- 실무에서는 표준 컨테이너를 사용하는 것이 안전합니다.
체크 질문 (스스로 답해보기)
- 새 노드를 왜 Red로 삽입하는가?
- 삽입에서 "삼촌이 Red"와 "삼촌이 Black"일 때 처리가 왜 달라지는가?
- RBT가 AVL보다 덜 엄격한 균형인데도
O(log N)을 보장하는 이유는?
李家네_공부방