루트 노드가 BLACK이라는 2번 속성 위반 → 루트 노드 색을 BLACK으로 변경 (50)
🔹 insert 20
삽입 노드의 색깔은RED (20)
🔹 insert 10
삽입 노드의 색깔은 RED (10)
4번 속성 위반! (RED 노드의 자식은 무조건 BLACK이어야 함!)
RED가 한 쪽으로 몰려 있으니 RED 하나를 반대편으로 옮겨주자!
구조를 바꾼 이후에도 BST의 특징 또한 유지되어야 한다는 것을 잊지 말자.
구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다.
4번 속성 위반을 해결하기 위해 RED 하나를 넘겨야 하는데, BST의 특징 또한 유지하면서 넘기려면 회전을 사용해야 한다. → 회전을 어떻게 사용할 지가 관건!
20과 50의 색을 바꿔준다 → 20, 50
50을 기준으로 오른쪽으로 회전한다
[Case 3] RED 삽입 후 4번 속성을 위반했을 때 (RED의 자식이 RED인 경우): 🔹 삽입된 RED 노드가 부모의 왼쪽 자녀 and 부모도 RED고 할아버지의 왼쪽 자녀 and 삼촌(부모의 형제)가 BLACK이면 → 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전한다 🔹 삽입된 RED 노드가 부모의 오른쪽 자녀 and 부모도 RED고 할아버지의 오른쪽 자녀 and 삼촌(부모의 형제)가 BLACK이면 → 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 왼쪽으로 회전한다
🔹 insert 40
삽입 노드의 색깔은RED (40)
4번 속성 위반!
위의 case 3괴 다른 점은, 삽입된 노드를 기준으로 할아버지까지의 경로가 꺾였다는 점
꺾인 부분을 펴줘서 위 case 3과 같은 형태로 만들면 위 case 3과 같은 방식으로 해결 가능!
20을 기준으로 왼쪽으로 회전
40과 50의 색을 바꿔준다 → 40, 50
50 기준으로 오른쪽으로 회전한다
[Case 2] RED 삽입 후 4번 속성을 위반했을 때: 🔹 삽입된 RED 노드가 부모의 오른쪽 자녀 and 부모도 RED고 할아버지의 왼쪽 자녀 and 삼촌은 BLACK이라면 → 부모를 기준으로 왼쪽으로 회전한 뒤 Case 3의 방식으로 해결 🔹 삽입된 RED 노드가 부모의 왼쪽 자녀 and 부모도 RED고 할아버지의 오른쪽 자녀 and 삼촌은 BLACK이라면 → 부모를 기준으로 오른쪽으로 회전한 뒤 Case 3의 방식으로 해결
🔹 insert 30
삽입 노드의 색깔은RED(30)
4번 속성 위반!
앞의 두 case와는 다르게, RED가 한쪽으로 몰려 있지 않아서 옮길 수가 없다😵
4번 속성을 만족시키면서 5번 속성을 유지하려면, 10과 50을 BLACK으로 바꾸고 20을 RED로 바꾸면 된다
[Case 1] RED 삽입 후 4번 속성을 위반했을 때: 삽입된 RED 노드의 부모도 RED and 삼촌도 RED라면 → 부모와 삼촌을 BLACK으로 바꾸고 할아버지를 RED로 바꾼 뒤 할아버지에서 다시 확인을 시작한다
📝 슈도코드 작성하기
while (부모가 RED) {
// CASE 1.
if 부모/삼촌 == RED이면,
부모/삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경
할아버지에서 다시 시작
// CASE 2/3. 삼촌 == BLACK
else {
// CASE 2.
if 할아버지/부모/자신 꺾인상테
회전해서 부모/자신을 펴준다. CASE 3 상태가 됨
// CASE 3. 할아버지/부모/자신 펴진상테
부모/할아버지 서로 색바꾸기
할아버지 기준 회전
}
}
// 종료전
루트를 BLACK으로 변경
RB 트리 삭제
삭제 Overview
삭제 전 RB 트리 속성을 만족한 상태
삭제 방식은 일반적인 BST와 동일
삭제 후 RB 트리 속성 위반 여부 확인
RB 트리 속성을 위반했다면 재조정 (delete-fixup)
RB 트리 속성을 다시 만족
속성 위반 여부 확인
RB 트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요하다!
1️⃣ 삭제하려는 노드의 자녀가 없거나 하나라면, 삭제되는 색 = 삭제되는 노드의 색
(여기서는 유효한 값을 가지는 자녀를 의미함. 즉, NIL 노드는 포함하지 않음)
25 삭제 → RED 삭제
80 삭제 → BLACK 삭제
40 삭제 → BLACK 삭제
2️⃣ 삭제하려는 노드의 자녀가 둘이라면, 삭제되는 색 = 삭제되는 노드의 후임자successor의 색
20 삭제 → 후임자 = 25 → RED 삭제
35 삭제 → 후임자 = 37→ RED 삭제
50 삭제 → 후임자 = 80→ BLACK 삭제
삭제되는 색이 RED라면, 어떠한 속성도 위반하지 않는다.
삭제되는 색이 BLACK이라면, 2, 4, 5번 속성을 위반할 수 있다. → 재조정 필요!
40 삭제 → BLACK 삭제 → 4, 5번 속성 위반!
2번 속성 위반 해결하기
→ 루트 노드를 BLACK으로 바꾸면 된다
35 삭제 전
35 삭제 → BLACK 삭제 → 50이 루트 노드가 되고 2번 속성 위반 → 50을 BLACK으로 바꿔 해결 (50)
35 삭제 후
삭제 후 5번 속성 위반 시 EXTRA BLACK 부여
삭제되는 색이 BLACK일 때, 특수한 상황을 제외하면 5번 속성을 항상 위반하게 된다. 5번 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 EXTRA BLACK을 부여한다.
경로에서 BLACK 수를 카운트할 때, EXTRA BLACK은 하나의 BLACK으로 카운트된다.
🔹 delete 10
10 삭제 전
10 삭제 → BLACK 삭제 → 5번 속성 위반!
EXTRA BLACK을 부여해서 5번 속성을 다시 만족시켜야 한다
10 삭제 후
삭제한 색의 위치를 대체한 노드에 EXTRA BLACK을 부여해야 한다.
삭제된 색은 10의 BLACK이므로 10의 위치를 대체한 노드인 NIL 노드에 EXTRA BLACK을 부여
20의 black height는 NIL의 BLACK에 EXTRA BLACK까지 2가 된다. 30을 통해서도 30, NIL로 2다. 즉, 5번 속성을 만족하게 된다.
NIL과 같이 EXTRA BLACK이 부여된 BLACK 노드를 DOUBLY BLACK 노드라고 부른다.
🔹 delete 30
30 삭제 전
30 삭제 → 30은 자녀가 하나라서 삭제되는 색은 BLACK
30 삭제 후
5번 속성 위반이므로EXTRA BLACK 부여
삭제된 색은30의BLACK이었으므로, 30을 대체한 노드인 25에 EXTRA BLACK 부여
25에 EXTRA BLACK 부여 이후
25에 EXTRA BLACK 부여 후 다시 5번 속성 만족
25와 같이 EXTRA BLACK이 부여된 RED 노드를 RED-AND-BLACK 노드라고 부른다.
🔹 delete 50
50 삭제 전
50은 자녀가 둘이라서 삭제되는 색은 50의 후임자인 80의 BLACK → 5번 속성 위반!
50 삭제 후
80의 위치를 대체한 NIL 노드에 EXTRA BLACK 부여 → 5번 속성 다시 만족
삭제되는 색이 BLACK이고, 5번 속성 위반일 때: EXTRA BLACK을 부여받은 노드는 DOUBLY BLACK이 되거나 RED-AND-BLACK이 된다.
🔸 RED-AND-BLACK 해결하기
→ RED-AND-BLACK을 BLACK으로 바꾸면 해결
30을 삭제하면 4번, 5번 속성 위반
30을 대체한 25에 EXTRA BLACK 부여
25는 RED-AND-BLACK이 되었으니 그냥 BLACK으로 바꿔주면 끝!
🔸 DOUBLY BLACK 해결하기
→ 결국 어떻게 EXTRA BLACK을 없앨것인지가 관건
→ 네 가지의 case로 분류할 때의 기준은 DOUBLY BLACK의 형제의 색과, 그 형제들의 자녀의 색
4️⃣ DOUBLY BLACK의 오른쪽 형제가 BLACK and 그 형제의 오른쪽 자녀가 RED일 때:
→그 RED를 DOUBLY BLACK 위로 옮기고, 옮긴 RED로 EXTRA BLACK을 전달해서 RED-AND-BLACK으로 만들기
→RED-AND-BLACK을 BLACK으로 바꿔서 해결
바꾸기 전
→ 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 BLACK으로, 부모는 BLACK으로 바꾼 후에
바꾼 후
→ 부모를 기준으로 왼쪽으로 회전하면 해결
회전 이후
Case 4
[Case 4] 🔹 DOUBLY BLACK의 오른쪽 형제가 BLACK and 그 형제의 오른쪽 자녀가 RED일 때: → 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 BLACK으로, 부모는 BLACK으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결 🔹DOUBLY BLACK의 왼쪽형제가BLACKand 그 형제의왼쪽자녀가RED일 때: →왼쪽형제는 부모의 색으로,왼쪽형제의왼쪽자녀는BLACK으로, 부모는BLACK으로 바꾼 후에 부모를 기준으로오른쪽으로 회전하면 해결
3️⃣ DOUBLY BLACK의 오른쪽 형제가 BLACK and 그 형제의 왼쪽 자녀가 RED and 그 형제의 오른쪽 자녀는 BLACK일 때:
→DOUBLY BLACK의 형제의 오른쪽 자녀가 RED가 되게 만들어서 이후에는 Case 4를 적용해 해결
바꾸기 전
→ E 위치에 RED가 오도록 만들기 위해 C와 D의 색을 바꾼 후에
바꾼 후
→D를 기준으로 오른쪽으로 회전하면 된다
회전 이후
→ 이제 Case 4를 적용해서 해결한다.
→ C는 B의 색으로, B와 D는 BLACK으로 바꾼 후 B를 기준으로 왼쪽으로 회전하면 해결
Case 4 적용 후
Case 3
[Case 3] 🔹DOUBLY BLACK의오른쪽형제가BLACKand 그 형제의왼쪽자녀가RED and 오른쪽 자녀가 BLACK일 때: →DOUBLY BLACK의형제의 오른쪽 자녀를 RED가 되게 만들어서 이후에는 Case 4를 적용하여 해결 🔹DOUBLY BLACK의왼쪽형제가BLACKand 그 형제의오른쪽자녀가RED and 왼쪽 자녀가BLACK일 때: →DOUBLY BLACK의형제의 왼쪽 자녀를 RED가 되게 만들어서 이후에는 Case 4를 적용하여 해결
2️⃣ DOUBLY BLACK의 형제가 BLACK and 그 형제의 두 자녀가 모두 BLACK일 때:
→DOUBLY BLACK과 그 형제의 BLACK을 모두 모아서 부모에게 전달해서 부모가 EXTRA BLACK을 해결하도록 한다
BLACK을 모아 부모에게 전달하기 전
→ A와 A의 형제인 D의 BLACK을 모아서 부모에게 전달하게 되면
→ A와 D에서 BLACK을 모았기 때문에 A는 여전히 BLACK이고 D는 RED가 된다
모은 BLACK을 부모에게 전달한 후
→ BLACK을 전달받은 B는 RED-AND-BLACK 또는 DOUBLY BLACK이 된다 (5번 속성은 여전히 만족됨)
→ B가 RED-AND-BLACK이 됐다면 BLACK으로 바꿔주면 상황은 종료되지만
→B가 DOUBLY BLACK이 됐다면: B가 루트 노드라면 BLACK으로 바꿔서 해결, 아니라면 Case 1, 2, 3, 4 중 하나로 해결
Case 2
[Case 2] DOUBLY BLACK의 형제가 모두 BLACK and 그 형제의 두 자녀가 모두 BLACK일 때 → DOUBLY BLACK과 그 형제의BLACK을 모두 모아서 부모에게 전달해서 부모가EXTRA BLACK을 해결하도록 한다
1️⃣ DOUBLY BLACK의 형제가 RED일 때:
→DOUBLY BLACK의형제를BLACK으로 만든 후 Case 2, 3, 4 중에 하나로 해결
→ B를 기준으로 왼쪽으로 회전하면 DOUBLY BLACK A의 형제는 C가 되며, 즉 BLACK이 된다
→ 회전 후에도 5번 속성을 만족하려면 왼쪽으로 회전하기 전에 B와 D의 색을 바꿔준다
B와 D의 색을 바꾼 모습회전 후
→DOUBLY BLACK의형제가 BLACK이 되었으므로 Case 2, 3, 4 중에 해결책을 찾으면 된다.
Case 1
[Case 1] 🔹DOUBLY BLACK의오른쪽형제가 RED일 때: → 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 DOUBLY BLACK을 기준으로 Case 2, 3, 4 중 하나로 해결 🔹DOUBLY BLACK의왼쪽형제가RED일 때: →부모와 형제의 색을 바꾸고 부모를 기준으로 오른쪽으로 회전한 뒤DOUBLY BLACK을 기준으로 Case 2, 3, 4 중 하나로 해결
BLACK 삭제 시 5번 속성 위반 해결 방법 요약
삭제되는 색이 BLACK일 때 삭제되는 색이 있던 위치를 대체한 노드에 EXTRA BLACK을 부여한다
대체한 노드가 RED-AND-BLACK이 되었다면 BLACK으로 바꿔주면 끝
대체한 노드가 DOUBLY BLACK이 되었다면 Case 1, 2, 3, 4 중에 하나로 해결
📝 슈도코드
while (타겟이 루트아님 && 타겟 == BLACK) {
// CASE 1.
if 형제 == RED
형제/부모 서로 색바꾸기, 부모기준 회전 (타겟이 내려가도록)
// CASE 2.
if 형제 == BLACK, 형제의 자식 둘다 블랙
형제/자신의 블랙을 부모로 올리기 -> 형제를 RED로 변경, 부모에서 다시 fixup
else {
// CASE 3.
if 형제 == BLACK, (형제의 꺾인 자식) == RED
자식 RED와 형제 서로 색바꾸기, 펴지게 회전 (RED가 바깥쪽에 오게)
CASE 4가 됨
// CASE 4. 형제 == BLACK, (형제의 펴진 자식) == RED
부모/형제 서로 색바꾸기
형제의(펴진 자식) = BLACK
부모기준 회전 (타겟이 내려가도록)
타겟을 루트로 설정 -> while 종료
}
}
// 종료전
타겟을 BLACK으로 변경
