紅黑樹特性
- root 為黑色節點
- 所有 leaf 為黑色節點，值為 NIL
- 若某節點為紅色則其 child 為黑色 (無兩個連續紅色節點)
- 對任一節點，到 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 方法處理
