note
有以下五個特性:
- Every node is either Red or Black
- Every nil node is Black
- Every Red node has two Black child nodes
- Every path from node x down to a leaf node has the same number of Black nodes
- 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不能為紅色所以變成黑色