Red-Black 트리 (Red-Black Tree)

Red-Black 트리 (Red-Black Tree)

각 노드가 빨강 또는 검정 색상을 가지며 5가지 규칙을 만족하여 근사 균형을 유지하는 자가 균형 이진 탐색 트리로, AVL보다 느슨한 균형으로 삽입·삭제가 빠름

목적: 근사 균형, 빠른 삽입·삭제, O(log n) 보장, 실용적 성능

특징: 색상 속성, 느슨한 균형, 회전+색상 변경, 널리 사용

5가지 규칙

균형 보장: 최대 높이 ≤ 2log₂(n+1), 최악 경로가 최선 경로의 2배 이내

동작: 삽입(빨강으로 삽입 → 규칙 위반 시 회전+색상 변경), 삭제(복잡한 케이스 처리)

시간 복잡도: 검색·삽입·삭제 모두 O(log n) 보장

공간 복잡도: O(n) + 색상 1비트

장점: 근사 균형, 빠른 삽입·삭제, O(log n) 보장, 적은 회전, 실용적

단점: 구현 복잡도, AVL보다 느린 검색, 색상 관리

적용사례: Java TreeMap/TreeSet, C++ std::map/set, Linux 커널, 메모리 할당자, DB 인덱스

비교: Red-Black(느슨/빠른삽입/높이2배) vs AVL(엄격/빠른검색/높이1배)

연관: BST, AVL 트리, 균형 트리, 색상, 회전