紅黑樹特性
- root 為黑色節點
- 所有 leaf 為黑色節點，值為 NIL
- 若某節點為紅色則其 child 為黑色 (無兩個連續紅色節點)
- 對任一節點，到 leaf 所經過的黑色節點數量一樣
為了符合以上特性，插入或刪除節點時需要作一些調整
刪除節點
按照 binary search tree 的方式處理節點 x (successor/predecessor y 的值移至 x，將 y 刪除)
示範圖說明
- 為樹的一部份，不是完整的樹喔~
- 灰色的點表示可以是紅的或黑的
Case 0: x 和 y 原本的顏色為一黑一紅
- x 設為黑色
Case 1: x 的 sibling w 為紅色
- 以 x.p 為圓心，w 往上轉
- x.p 和 w 顏色互換
- 現在 x 有新的 sibling w (新的 w 是舊的 w 的小孩，必定為黑色) 繼續用 case2, 3, 4 處理
Case 2: x 的 sibling w 為黑色，w 的小孩皆為黑色
- w 設為紅色
- x.p 設為黑色
- 如果 x.p 原本是紅色，x.p 設為黑色，處理結束
- 如果 x.p 原本是黑色，x.p 視為新的 x，重新處理
Case 3: x 的 sibling w 為黑色，w 的右小孩為黑色，左小孩為紅色
- 以 w 為圓心，左小孩往上轉
- w 和左小孩顏色互換
- 左小孩成為新的 w，繼續用 case 4 處理
Case 4: x 的 sibling w 為黑色，w 的右小孩為紅色
- 以 x.p 為圓心，w 往上轉
- w 設為 x.p 原本的顏色
- x.p 和右小孩設為黑色
