[C] 레드블랙 트리 (삭제)

방법이있지·2025년 6월 20일

[정글 4-8주차] C언어

목록 보기

20/26

~~제 블랙핑크 최애곡은 셧다운, 레드벨벳 최애곡은 피카부입니다~~

참고 자료

본 글은 간결성을 위해 엄밀한 증명, 검증은 생략했습니다.

한마디로 나중에 C언어로 직접 구현할 때, 기억해야 할 부분만 적어 놨습니다.

추가적인 부분 (e.g., 왜 이렇게 삭제를 해도 레드블랙 트리의 성질이 유지되는지...)이 궁금하시면 참고 자료 시청을 권해 드립니다.

삭제된 노드의 자식이 2개일 때
- 실제로 삭제되는 색은, 삭제되는 노드의 Successor의 색임을 기억할 것
- Successor는 삭제되는 노드의 오른쪽 서브트리의 최솟값 노드

아무 속성도 위반되지 않음
1번: 모든 노드는 Red 또는 Black, 3번: 모든 Nil 노드는 Black
- 당연히 위반될 리가 없음
2번: 루트 노드는 Black /
- Red 노드가 삭제됐으니, 루트 노드 / Nil 노드가 삭제됐을 리가 없음
4번: Red 노드의 자식은 무조건 Black 노드
- 삭제된 노드는 Red이므로, 삭제된 노드의 자식은 무조건 Black
- 즉 Red 부모가 새로운 Red 자식을 가지는 상황은 있을 수 없음
5번: 특정 노드 x에서 어느 Nil 노드로 내려가든, 경로에서 마주치는 Black 노드 수는 동일
- Red가 삭제돼도 Black의 수는 달라지지 않음

Black인 경우, 삭제 위치의 새로운 노드를 Doubly Black으로 지정함
- Black Height를 계산할 때, 2개의 Black 노드로 간주됨
- 물론 정상적인 노드가 아니므로, 아래 과정을 통해 해결해야 함

DB의 형제의 색과, 형제의 자녀들의 색에 따라 해결법이 달라짐
- 본 글은 과정 위주로만 서술했습니다. 원리에 입각한 설명이 궁금하시면, 위 참고영상 시청을 권장드립니다

DB가 왼쪽 자식인 경우

오른쪽 형제	형제의 왼쪽 자녀	형제의 오른쪽 자녀	Case 몇번?
Black	상관없음	Red	Case 4
Black	Red	Black	Case 3
Black	Black	Black	Case 2
Red	상관없음	상관없음	Case 1

DB가 오른쪽 자식인 경우

왼쪽 형제	형제의 왼쪽 자녀	형제의 오른쪽 자녀	Case 몇번?
Black	Red	상관없음	Case 4
Black	Black	Red	Case 3
Black	Black	Black	Case 2
Red	상관없음	상관없음	Case 1

조건 1: DB의 오른쪽 형제가 Black이며 형제의 오른쪽 자녀가 Red일 때

조건 2: DB의 왼쪽 형제가 Black이며 형제의 왼쪽 자녀가 Red일 때

조건 1: DB의 오른쪽 형제가 Black, 형제의 왼쪽 자녀가 Red, 형제의 오른쪽 자녀가 Black일 때

조건 2: DB의 왼쪽 형제가 Black, 형제의 왼쪽 자녀가 Black, 형제의 오른쪽 자녀가 Red일 때

조건: DB의 형제가 Black, 형제의 두 자식이 모두 Black일 때

(1) DB를 일반 Black으로 되돌리고, 형제를 Red로 변경
(2a) 부모가 Red면, Black으로 변경
(2b) 부모가 Black이면, 부모는 Doubly Black이 되어 버림
- 부모가 루트 노드면, 단순히 다시 Black으로 바꿔 해결
- 부모가 루트가 아니면, Case 1 ~ 4 중 알맞은 해결법으로 해결