Chapter 11 紅黑樹2 3 4轉紅黑 - Ian-Liu-1990/Data-Structure GitHub Wiki

紅黑樹

• 定義與條件

1. 每個節點非紅色，即黑色；

2. 根節點是黑色；

3. 每個葉節點（NIL或者空節點）是黑色；

4. 如果一個節點是紅色，則它的兩個子節點都是黑色；

5. 對於每個節點，從該節點到其所有後代葉節點的路徑上，均包含相同數目的黑色節點。

紅黑插入

1. 依照二分搜尋樹，插入適當位置且每次插入都以紅色節點插入

2. 查看有無叔父節點，若無代表插入為Root，直接紅色轉黑色，遵守2.

   • 若有叔父 : 檢查叔父紅或黑 :
     1. 叔父為紅-改變顏色 : 祖父B轉R，父親與叔父R轉B，若祖父剛好為Root - 在轉為黑遵守2.
     2. 叔父為黑-依照AVL調整 : 從祖父往父親方向檢查LR，LL，RL，RR，調整完中間節點必為B，兩子節點必為R

3. 若調整完發現有祖父節點與曾祖父節點發生連續紅違反4.，依照選轉由曾祖父往祖父方向在調整即可