Red-Black Tree레드-블랙 트리

레드-블랙 트리(Red-Black Tree)는 각 노드에 색(빨강/검정) 을 부여해 균형을 유지하는 자기 균형 이진 탐색 트리다. 삽입·삭제 후 회전과 색 변경으로 O(log n)을 보장한다. Java의 TreeMap, C++ STL의 map/set이 내부적으로 사용한다.

5가지 규칙

1. 1.모든 노드는 빨강 또는 검정
2. 2.루트는 검정
3. 3.리프(NIL) 노드는 검정
4. 4.빨강 노드의 자식은 반드시 검정 (빨강-빨강 금지)
5. 5.루트에서 임의의 리프까지 경로의 검정 노드 수는 동일

시간 복잡도

트리 높이 ≤ 2 log(n+1) 보장

AVL 트리 vs 레드-블랙 트리

사용 예시

// Java TreeMap — 내부적으로 레드-블랙 트리
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
// 자동 정렬: apple, banana, cherry

관련 개념

• •이진 트리 — 레드-블랙 트리의 기반
• •AVL 트리 — 또 다른 자기 균형 트리
• •해시맵 — TreeMap의 대안 (정렬 불필요 시)

참고문헌

• •Cormen et al. Introduction to Algorithms — Chapter 13