에듀테크 프로젝트 대시보드
레드-블랙 트리 (Red-Black Tree)
이진 탐색 트리는 값을 한쪽으로만 넣으면 한 줄로 늘어져 탐색이 O(n) 으로 느려진다.
레드-블랙 트리는 노드마다 빨강/검정 색을 두고 5가지 색 규칙을 항상 지키게 만들어,
삽입·삭제 때 회전과 재색칠로 스스로 균형을 잡는다. 그 결과 트리 높이가
2·log₂(n+1) 이하로 유지되어 탐색·삽입·삭제가 모두 O(log n) 이다.
아래에서 숫자를 넣어 보며 트리가 어떻게 다시 균형을 잡는지 관찰해 보자.
새 노드는 항상 빨강으로 삽입된다(검정 높이를 깨지 않으려고). 부모도 빨강이면 빨강-빨강 위반이 생기므로 아래 세 경우 중 하나로 고친다: ① 삼촌도 빨강 → 부모·삼촌을 검정, 조부모를 빨강으로 재색칠 후 조부모에서 다시 검사. ② 삼촌 검정 + 꺾인 모양 → 부모를 회전해 일직선으로 만든 뒤 ③으로. ③ 삼촌 검정 + 일직선 → 조부모를 회전하고 색을 맞바꾼다.
O(log n) 을 보장하는 핵심이다.
회전은 부모-자식 관계를 한 칸 돌리는 국소 연산이다. 중위 순회(in-order) 결과는 변하지 않으므로
이진 탐색 트리 성질이 유지된다. 딱 포인터 3쌍만 바꾸므로 O(1) 이다.
BST 규칙대로 새 노드 z 를 빨강으로 넣은 뒤, 부모가 빨강인 동안 아래 루프를 돈다.
재색칠만 한 경우 z 가 두 단계씩 위로 올라가므로 최악에도 O(log n),
회전은 최대 2번이면 끝난다.
| 레드-블랙 트리 | AVL 트리 | |
|---|---|---|
| 균형 기준 | 색 규칙 (경로 검정 수) | 모든 노드의 좌우 높이차 ≤ 1 |
| 높이 상한 | ≈ 2·log₂n (느슨함) | ≈ 1.44·log₂n (빡빡함) |
| 탐색 속도 | 약간 느림 (트리가 더 깊을 수 있음) | 더 빠름 |
| 삽입/삭제 회전 | 삽입 ≤ 2, 삭제 ≤ 3 (적음) | 삭제 시 루트까지 O(log n) 번 가능 |
| 쓰이는 곳 | C++ std::map, Java TreeMap, 리눅스 커널 CFS 스케줄러·epoll | DB 인덱스, 읽기가 압도적으로 많은 경우 |
O(log n) 을 보장한다는 점은 같다.