## 紅黑樹特性

1. root 為黑色節點
2. 所有 leaf 為黑色節點，值為 NIL
3. 若某節點為紅色則其 child 為黑色 (無兩個連續紅色節點)
4. 對任一節點，到 leaf 所經過的黑色節點數量一樣

為了符合以上特性，插入或刪除節點時需要作一些調整

## 新增節點

按照 binary search tree 的方式將新節點 x 插入，並設為紅色

### Case 0: x 為 root

- 將 x 改為黑色

### Case 1: x 的父節點 x.p 為黑色

- 直接插入即可，不影響回黑樹特性

### Case 2: x 的父節點 x.p 為紅色，x 的 uncle y 為紅色

- x.p 和 y 改為黑色
- x.p.p 改為紅色 (根據上面提到的特性 3，x.p.p 原本一定是黑節點)
- 將 x.p.p 設為新的 x，繼續調整紅黑樹


### Case 3: x 的父節點 x.p 為紅色，x 的 uncle y 為黑色，x.p.p, x.p, x 為一直線

- 以 x.p.p 為圓心，將 x.p 旋轉上去
- x.p 改為黑色， x.p.p 改為紅色


### **Case 4**: x 的父節點 x.p 為紅色，x 的 uncle y 為黑色，x.p.p, x.p, x 非一直線

- 以 x.p 為圓心，將 x 旋轉上去 (x.p.p, x.p, x 會變成一直線)
- 用 case 3 方法處理


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