1. 데이터 삭제
일반적으로 이진 탐색 트리와 동일하게 작동한다.
하지만 색상을 변경하는 부분이 추가된다.
(1) 삭제할 노드가 Red인 경우
BST의 삭제 알고리즘으로 해당 노드를 제거하면 된다.
(2) 삭제할 노드가 Black인 경우
어떤 노드로부터 하위 리프 노드에 도달하는 모든 경로에는 같은 개수의 블랙 노드를 만나야 한다.
(왼쪽 : 10 - 5 - NIL, 2개의 Black 노드 / 오른쪽 : 10 - 20 - NIL, 1개의 블랙노드)
따라서 BST의 삭제 알고리즘 이후, 같은 개수의 블랙 노드를 만나게 하기 위하여
NIL 노드를 두 개 가지고 있도록(중첩시켜 ; Double Black) 만들 수 있다.
그리고 중첩된 black 하나를 하나씩 위로 올리면 된다.
2. 삭제할 노드가 Black인 여러 가지 경우
(1) root 노드가 Double Black 상태
- 중첩된 Black을 제거한다.
(2) DB인 노드의 형제 노드가 Red 일 때
- 형제(Sibling) 노드 : 같은 부모를 가지는 노드
(2-1) 형제 노드와 부모 노드의 색상 교환
(2-2) DB 방향으로 회전(위 그림에서는 좌측 회전)
(2-3) 형제를 갱신함
(3) DB의 형제가 Black, 형제의 양쪽 자식이 모두 Black인 경우
(3-1) DB의 Black 하나를 부모로 올림
(3-2) 형제를 Red로 바꿈
- 우측 경로에서 leaf 노드까지의 거리를 같게 하기 위함이다.
(4) DB의 형제가 Black, 형제의 자식 중 가까운 자식이(near) Red, 먼 자식이(far) Black인 경우
(4-1) near 자식 노드를 Black으로 바꿈
(4-2) 형제 노드를 Red로 바꿈
(4-3) far 방향으로 회전(사진에서는 형제 노드를 우측 회전) => 이후 5번 실행
(5) DB의 형제가 Black, 형제의 자식 중 먼 자식이(far) Red 인 경우
(5-1) 부모와 형제의 색상을 교환
(5-2) far 노드의 색상을 black으로 설정
(5-3) 부모를 기준으로 DB 방향으로 회전(사진 상 왼쪽 회전)
(5-4) 추가된 Black을 제거하여 DB 상태를 풀어줌
'자료구조와 알고리즘 > 탐색 트리 & 최소 스패닝 트리' 카테고리의 다른 글
| 6-1. 상호 배타적 집합 (Disjoint Set) (0) | 2023.07.20 |
|---|---|
| 4-5. 레드-블랙 트리(RBT ; Red-Black Tree) - (3) 데이터 삭제 구현 (0) | 2023.07.18 |
| 4-3. 레드-블랙 트리(RBT ; Red-Black Tree) - (1) (0) | 2023.07.18 |
| 4-2. 이진 탐색 트리(BST ; Binary Search Tree) (0) | 2023.07.14 |
| 4-1. 이진 탐색(Binary Search) (0) | 2023.07.13 |