2025.04.18
TIL(TODAY I LEARN)
-
오늘한 내용 : 고급 자료 구조 :RED-BLACK-TREE 개념 정리
-
WEEK06: 메모리 누수, 균형 이진 탐색 트리(AVL Tree, Red-Black Tree)
-
너무 너무 헷갈린다. 고려해야 할 점이 너무 많음!
Red-Black Tree
- 이진 탐색 트리(Binary Search Tree)의 일종으로, 데이터를 정렬된 상태로 저장하면서 트리의 균형을 유지하는 데 초점을 맞춘 자료구조
일반적인 이진 검색 트리와 레드 블랙 트리왜 필요한가?
일반적인 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우칠 수 있어 최악의 경 우 O(n)의 성능을 가짐.
RB트리는 자동으로 균형을 맞추기 때문에 항상 O(log n)의 시간 복잡도를 보장.
RB트리의 5가지 속성
1. 노드는 빨강 또는 검정이다.
2. 루트는 항상 검정이다.
3. 모든 리프(NIL)는 검정이다. (리프는 실제 데이터가 아닌 NULL 포인터)
4. 빨강 노드의 자식은 반드시 검정이다. (빨강이 연속될 수 없음)
5. 어떤 노드에서 리프까지 가는 모든 경로에는 같은 수의 검정 노드가 있다.
이 속성들을 지키면서 노드 삽입/삭제 시마다 자동으로 트리를 재조정(회전 및 색상 변경)하여 균형을 유지.
| 연산 | 시간 복잡도 |
|---|---|
| 검색 | O(log n) |
| 삽입 | O(log n) |
| 삭제 | O(log n) |
검색 (Search)
- 이진 검색 트리와 동일
삽입 (Insert)
- 새 노드(x)는 Red로 추가.
- RB트리의 속성이 깨지는 경우, 회전 및 색상 변경을 통해 수정
- 새 노드(x)는 항상 맨 아래쪽에
- x의 부모노드가 Black → 삽입 완료(x는 RED)
- x의 부모노드가 Red → 룰 위반 - (Case1, Case2)
레드 블랙 트리 특성에 따라 부모 노드 p가 레드라면 부모 노드 p의 부모 p² 는 반드시 블랙이다.
레드 블랙 트리 특성에 따라 x의 형제 노드도 반드시 블랙이다. (Rule 4)
x 주변에서 레드와 블랙 두 가지 다 가능한 것은 p의 형제 노드 s(x의 삼촌 노드) 뿐이다.
-
x의 부모노드(p)가 Red
Case 1) x의 삼촌노드(s)가 Red
- p와 s 의 색을
Red→Black - p²의 색을
Red로
- p²가 root → p²를Black으로 (Rule 2)
- p²가 root가 아님 → p²의 부모(p³)의 색 확인
- p³가 Black → 끝
- p³가 Red → p²를 문제 발생 노드로 → Case1, Case2 고려해 재귀 반복(p² is not root) ----------------------------------------------------- 삽입 전 (Red-Red 위반 발생) 수선 후 (색상 변경) / / [B] p² [R] p² / \ / \ [R] p [R] s ===> [B] p [B] s / / [R] x [R] x
Case 2) s가
Black또는NULL- Case 2-1) x가 p의 오른쪽 자식
- p 중심으로 왼쪽 회전 → Case 2-2) 적용 가능해짐
- Case 2-2) x가 p의 왼쪽 자식
- p²를 중심으로 오른쪽 회전 → p², 현재 p²의 부모의 색을 바꾼다.
- p와 s 의 색을
Case 2-1: x가 오른쪽 자식
(좌회전 전)
[B] p²
/
[R] p
\
[R] x
-- 좌회전 (p 중심) -->
Case 2-2 구조로 변경
(이제 x가 p²의 왼쪽 자식)
[B] p²
/
[R] x
/
[R] p
-- 우회전 (p² 중심) & 색상 교환(p²와 회전 후 p² 위 올라온 노드) -->
최종 구조 (Red-Black 속성 회복)
[B] x
/ \
[R] p [R] p²- Case 2를 만나면 어떻게든 Case 2 - 2의 수선을 마지막으로 종료.
- Case 1을 만나면 Case 1에서 종료가 될 수도 혹은 다른 노드에서 수선이 진행될 수 있음.
회전 (Rotation)
트리의 일부 구조를 재배열하여 이진 탐색 트리의 성질을 유지하면서, 균형을 맞추는 연산.
| 종류 | 기준 노드 | 결과 방향 |
|---|---|---|
| 좌회전 (Left Rotation) | 현재 노드 | 오른쪽 자식이 위로 올라감 |
| 우회전 (Right Rotation) | 현재 노드 | 왼쪽 자식이 위로 올라감 |
- 모든 회전 연산에는 서브트리 재배치가 반드시 포함
- 서브트리 재배치
- 회전은 단순히 "노드 위치만 바꾸는 게 아니라" 기존 트리의 왼쪽-오른쪽 정렬 성질(BST 성질)도 반드시 유지해야 하기 때문.
def left_rotate(p):
x = p.right
p.right = x.left # ← 서브트리 재배치
x.left = p
# 부모 포인터 업데이트 등 추가
def right_rotate(p2):
p = p2.left
p2.left = p.right # ← 서브트리 재배치
p.right = p2
# 부모 포인터 업데이트 등 추가삭제 (Delete)
삭제는 BST 삭제 방식 + RB트리 규칙 수선 작업의 결합.
- BST 방식으로 삭제
- 삭제 대상 노드(x)를 찾는다
- 노드 x가:
- 리프(자식 없음) → 바로 제거
- 자식 1개 → 자식을 올려치기
- 자식 2개 → 중위 후속 노드(successor)로 교체하고 후속 노드를 삭제
- 삭제 후 문제 발생 여부 확인
- 삭제된 노드나 대체된 노드가 BLACK일 때, → RB트리 규칙이 깨질 수 있음 (특히, Rule 5: 흑 높이 보존)
- 삭제된 노드나 대체된 노드가 BLACK일 때, → RB트리 규칙이 깨질 수 있음 (특히, Rule 5: 흑 높이 보존)
- Fix-up(수선) 단계 돌입
- 색상 변경 / 회전 / 더블블랙 해결
- Case 1~4 형태로 반복적으로 처리
- 더블 블랙?
- BLACK 노드가 삭제되었는데, 자식도 BLACK(NIL 포함)이면 → 그 경로는 BLACK 개수가 하나 부족 하게 됨 → 이 위치를 임시로 "BLACK이 2개 있는 것처럼" 표시 = Double Black
- BLACK 노드가 삭제되었는데, 자식도 BLACK(NIL 포함)이면 → 그 경로는 BLACK 개수가 하나 부족 하게 됨 → 이 위치를 임시로 "BLACK이 2개 있는 것처럼" 표시 = Double Black
레드-블랙 트리 삭제
| Case | 삭제 노드 색 | 조건 | 주요 동작 |
|---|---|---|---|
| Case 0 | 🔴 RED | 자식이 있든 없든 | 그냥 삭제만 하면 됨. 수선 불필요 |
| Case 1 | ⚫ BLACK | 형제(s)가 RED | s↔p 색 교환 → p 기준 회전 → 새로운 형제로 Case 2~4 적용 |
| Case 2 | ⚫ BLACK | 형제(s)가 BLACK, 형제의 자식 둘 다 BLACK | (1) 부모(p)가 RED :형제를 RED, 부모를 BLACK으로 바꾸면 DB가 완전히 해소 → 종료 //// (2) 부모(p)가 BLACK:형제를 RED, DB를 한 단계 위(parent)로 전이 → 다시 Case 1~4 검사 |
| Case 3 | ⚫ BLACK | 형제 BLACK, 가까운 자식이 RED | s 기준 회전 → 가까운 자식 ↔ s 색 교환 → Case 4로 전환 |
| Case 4 | ⚫ BLACK | 형제 BLACK, 먼 자식이 RED | p↔s 색 교환 → p 기준 회전 → 먼 자식을 BLACK으로 칠하면 DB 해소 → 종료 |
🌳 예시: 키 5 삭제 후 수선(Case 1,2)
초기 트리:
[B]10
/ \
[B] 5 [R]15
/ \
[B]12 [B]20
- 삭제 대상:
[B]5→ 왼쪽 자리 NIL에 Double Black 발생
✅ Case 1 (형제 RED)
- DB 위치: 10의 왼쪽
NIL - 부모: 10(B), 형제: 15(R)
처리:
- 색 교환:
10→R,15→B - 10 기준 좌회전
[B]15
/ \
[R]10 [B]20
/ \
[BB]NIL [B]12
- 여전히 DB 존재 → 다음 Case
✅ Case 2 (형제·자식 모두 BLACK, 부모 RED)
- DB 위치: 10의 왼쪽 NIL
- 형제: 12(B)
- 부모 10은 RED
처리:
12→RED,10→BLACK→ DB 해소 → 종료
[B]15
/ \
[B]10 [B]20
\
[R]12
참고: 본 예시에서는 Case 3·4가 전혀 발생하지 않습니다.
🌳 예시 2: Case 3 → Case 4 발생 예시
초기 트리:
[B]8
/ \
[B]3 [B]12
/ \ / \
[B]1 [B]6 [B]10 [B]14
/ \
[R]4 [R]7
- 삭제 대상:
[B]1→ 3의 왼쪽 자리NIL에 Double Black 발생
✅ Case 3 (형제 BLACK, 가까운 자식 RED)
- DB 위치: 3의 왼쪽 NIL
- 부모: 3(B), 형제: 6(B), 가까운 자식: 4(R)
처리:
- 색 교환:
6 ↔ 4→ 6(R), 4(B) 6기준 우회전
[B]8
/ \
[B]3 [B]12
/ \ / \
[BB]NIL [B]4 [B]10 [B]14
\
[R]6
\
[R]7
- 이제 구조가 Case 4 형태로 바뀜
✅ Case 4 (형제 BLACK, 먼 자식 RED)
- DB 위치: 3의 왼쪽 NIL
- 부모: 3(B), 형제: 4(B), 먼 자식: 6(R)
처리:
- 색 교환:
3 ↔ 4(둘 다 B → 변화 없음) 3기준 좌회전- 먼 자식(6) →
BLACK
[B]8
/ \
[B]4 [B]12
/ \ / \
[B]3 [B]6 [B]10 [B]14
/ \
[BB]NIL [R]7
- Double Black 완전히 해소 → 삭제 수선 종료
✅ 최종 트리
[B]8
/ \
[B]4 [B]12
/ \ / \
[B]3 [B]6 [B]10 [B]14
\
[R]7- 어려워도 너무 어렵다. 코드로 구현할 수 있을까?
^_^