## 紅黑樹特性

1. root 為黑色節點
2. 所有 leaf 為黑色節點，值為 NIL
3. 若某節點為紅色則其 child 為黑色 (無兩個連續紅色節點)
4. 對任一節點，到 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 和右小孩設為黑色


## 相關連結
[Red Black Tree Insertion | 紅黑樹新增節點](https://showsun63.blogspot.com/2025/01/RBT-insertion.html)
[Red Black Tree Visualization | 紅黑樹模擬器](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)