[C언어 - 알고리즘] Red-Black 트리 쉽게 이해하기: 삽입부터 균형 유지까지
🟥 Red-Black 트리 쉽게 이해하기: 삽입부터 균형 유지까지
이진 탐색 트리의 단점을 보완한 강력한 자료구조
균형, 색상, 회전으로 동작하는 Red-Black Tree 정리
🔍 Red-Black 트리란?
Red-Black Tree는 일반적인 BST(Binary Search Tree)에 균형 유지 조건을 더한 트리입니다.
트리의 높이를 일정하게 유지함으로써 탐색/삽입/삭제의 최악의 경우도 O(log n) 으로 제한할 수 있습니다.
🧱 왜 균형이 필요할까?
BST는 삽입 순서에 따라 한쪽으로 기울 수 있습니다.
그 결과, 탐색 성능이 O(n)까지 떨어질 수 있죠. Red-Black 트리는 이러한 문제를 예방합니다.
⚙️ Red-Black 트리의 5가지 속성
- 모든 노드는 Red 또는 Black
- 루트 노드는 항상 Black
- 모든 NIL 노드는 Black
- Red 노드는 Red 자식을 가질 수 없음 (Red 연속 금지)
- 어떤 노드에서 자손 NIL까지 가는 모든 경로에 포함된 Black 노드 수는 같아야 함
🧮 Black Height란?
특정 노드에서 자손 NIL까지 가는 경로에 포함된 검정 노드의 수 (자기 자신 제외)
RB 트리의 균형 조건인 5번 속성의 핵심 요소입니다.
🔄 색상 반전으로 균형 유지
두 자식이 Red일 경우, 부모-자식 모두 색을 반전하면
Black Height는 그대로 유지되며 트리 속성도 위배되지 않습니다.
🔧 삽입 규칙 요약
- 삽입은 BST처럼 진행
- 삽입된 노드는 항상 Red
- 삽입 후 RB 트리의 속성을 검사
- 위반 시 색상 변경 또는 회전(Rotation) 수행
🧪 삽입 예시
📌 insert(50)
50을 루트로 삽입할 경우, Red 상태로 시작합니다.
루트가 Red인 것은 허용되지 않으므로, 루트 색을 Black으로 변경합니다.
📌 insert(20)
20은 50보다 작으므로 왼쪽에 삽입됩니다.
BST 구조를 그대로 따릅니다.
🧩 삽입 Case 정리
✅ Case 3: Left-Left 삽입
연속된 Red가 생기면 회전과 색상 변경이 필요합니다.
✅ Case 2: Left-Right 삽입
삼촌이 Black이고 방향이 꼬이면, 먼저 회전해서 Case 3으로 바꿔야 합니다.
✅ Case 1: 부모와 삼촌이 모두 Red
이 경우는 색상만 변경해도 트리 속성을 회복할 수 있습니다.
예시 1
예시 2 (삼촌도 Red인 상태)
- 부모(R) → Black
- 삼촌(R) → Black
- 할아버지(B) → Red
→ 그 다음 할아버지를 기준으로 위로 올라가며 다시 검사
🧭 삽입 규칙 정리
| 케이스 | 조치 |
|---|---|
| Case 1 | 부모, 삼촌 Black으로 / 할아버지 Red |
| Case 2 | 부모 기준 회전 후 → Case 3 |
| Case 3 | 할아버지 기준 회전 + 색상 교체 |
✅ 마무리 요약
Red-Black Tree는 단순한 이진 탐색 트리보다 복잡한 규칙을 따르지만,
그만큼 항상 균형 잡힌 상태를 유지하며 탐색, 삽입, 삭제의 성능을 보장합니다.
이번 글에서는 삽입 시 발생하는 주요 케이스들을
그림과 함께 시각적으로 정리했기 때문에 실제로 구현하거나 이해할 때 큰 도움이 될 거예요.