R-B Tree

note

有以下五個特性:

1. Every node is either Red or Black
2. Every nil node is Black
3. Every Red node has two Black child nodes
4. Every path from node x down to a leaf node has the same number of Black nodes
5. The root node is always Black

Violation

Case1:

。Uncle is red(相鄰點y是紅色)

→做變色處理(change color)

Case2:

。uncle is black(相鄰點是黑色)，而且以AVL tree來看是LR或RL形式

→在p做Rotation，變成case3的狀態

Case3:

。uncle is black(相鄰點是黑色)，而且以AVL tree來看是LL或RR形式

→在g做Rotation，然後因為root不能為紅色所以變成黑色