레드-블랙 트리 (Red-Black Tree)
Source
Evernote/Technote scraps/레드-블랙 트리 - 위키백과, 우리 모두의 백과사전.md
Summary
레드-블랙 트리는 균형을 자동으로 유지하는(self-balancing) 이진 탐색 트리로, 삽입·삭제·검색 연산의 최악 시간 복잡도를 O(log n)으로 보장한다. 각 노드는 레드 또는 블랙 색상을 가지며, 루트와 리프는 블랙, 레드 노드의 자식은 모두 블랙, 모든 경로상의 블랙 노드 개수가 동일하다는 5가지 특성을 만족한다. AVL 트리보다 균형 조건이 느슨하여 회전 연산이 적고, 함수형 프로그래밍의 연관 배열 구현이나 실시간 시스템, 기하학 자료구조 등에 널리 활용된다. 구조적 이해를 위해 2-3-4 트리와 등장변환(isometry) 관계가 있음을 참고할 수 있다.
Key Points
- 균형 이진 탐색 트리: 삽입/삭제/검색의 최악 시간 복잡도 O(log n) 보장
- 5가지 특성: 1) 노드는 레드/블랙 중 하나, 2) 루트는 블랙, 3) 리프(NIL)는 블랙, 4) 레드 노드의 자식은 모두 블랙, 5) 모든 경로상 블랙 노드 개수 동일
- AVL 트리 대비 균형 조건이 느슨해 회전(rotations) 횟수가 적음
- 함수형 프로그래밍의 연관 배열/집합 구현, 실시간 처리, 기하학 알고리즘 등에 활용
- 2-3-4 트리와 구조적 대응(isometry) 관계로 동작 원리 이해에 도움