week-06

CLRS방식의 Deletion과의 차이점

Doubly Black 해소

Doubly Black의 형제가 Black인 경우


Assuming : DB is Left Child
형제의 자식 케이스 4가지

• : Left - Right

1. Black - Black
2. Red - Black
3. Red - Red
4. Black - Red
   
   

CLRS 방식
Case 1: Bottom up
Case 2: Change to Case 4 by rotation
Case 3, 4: Rotation


구현 방식
Case 1: Bottom up
Case 2, 3: Change to Case 4 by rotation
Case 4: Rotation


Proof Case 3 to Case 4


After Right Rotation


Black Inheritance


After Left Rotation


Black up to Parent

항상

• Black(Parent) -Black(L) - Black(R)

Summary

Deletion에서 Rotation을 한번 더 수행하여 Insertion에서 Rotation을 한번 아낄 수 있는 방식
장점 : X