2 紅黑樹 - Bo2SS

工程實現中應用非常廣泛

課程內容#

<5 個平衡條件>#

結點非黑即紅
根結點是黑色 [頭髮]
葉結點 (NIL) 是黑色 [不洗腳]
1. 通常不用畫出來，也不用考慮 NIL 結點，默認是黑色
紅色結點的兩個子結點都是黑色⭐
1. 紅色結點不能接紅色結點
從根結點到所有葉結點的路徑上，黑色結點數量相同⭐

平衡條件的認識#

4th+5th 條件 👉 在紅黑樹中，最長邊結點數量：最短邊結點數量 = 2 : 1
- 本質上，紅黑樹也是靠樹高控制平衡
紅黑樹比 AVL 樹的樹高控制條件更鬆散
- 所以在紅黑樹中插入或刪除結點以後，發生調整的概率更小，降低了調整損耗
Top-3 條件基本是廢話，想染什麼顏色就染什麼顏色，想變色就變色，NIL 默認就是黑色
- ❓ 如果沒有第 3 個條件，紅黑樹就不厲害了？但是不是默認是黑色的嗎

調整策略#

插入調整和刪除調整是分開的 [與 AVL 樹不同]

<關鍵點>#

①【插入調整，要站在祖父結點看】

向下看兩層
- 某結點與其子結點發生衝突時，某結點管不了
- “隔代親”：爺爺管兒子和孫子的事，不允許兒子打孫子
插入的結點一定是紅色，基於 5th 條件
- ❌插入黑色 —— 必然會調整 [一定會改變某條路徑上黑色結點的數量]
- ✅插入紅色 —— 可能會調整
[插入調整的目的] 解決雙紅情況

②【刪除調整，要站在父結點看】

向下看一層
發生的前提
- 刪除黑色 [參考二叉排序樹的刪除]
  - 度為 0⭐：特例 [NIL 起作用了]
    - 會產生一個雙重黑的 NIL 結點
    - 觸發刪除調整
  - 度為 1
    - 其唯一子孩子肯定是紅色，否則該結點一定會有另一棵子樹，來保證左右兩側的黑色結點數量相等，與度為 1 矛盾
    - 不會觸發刪除調整
  - 度為 2：可轉化為度為 0 或 1 的情況
- 刪除紅色：不影響平衡狀態
[刪除調整的目的] 解決雙黑情況

--> 總共5 種情況：插入 2 種 + 刪除 3 種

⭐關鍵關鍵⭐ —— 通用的調整策略
- 把每一種情況，想象成一棵大的紅黑樹中的局部子樹
  - 根結點可能還有 “長輩結點”，其它結點可能還有子樹
- 為了不影響全局，局部子樹的黑色結點數量在調整前、後相等
- [下面的每一種情況展現的都只是樹的一部分]
[PS] 如果根結點不是黑色，染個色就完事了 [不重要]

插入調整#

[目標] 解決雙紅情況

兩大類情況：4 + 4 種小情況

情況一#

【特點】叔叔結點為紅色
【策略】
- 修改三元組 <15 [1, 20]> 的小帽子
  - 黑紅紅👉紅黑黑：爺爺搶爸爸們的紅帽子
  - 保證各路徑的黑色結點數量不變
【圖示】紅色上浮
[PS]
- [圖中] 根結點的顏色一定是黑色，否則插入前根結點和子結點衝突，不平衡
- 包含 4 種小情況：插入結點x可以有四種位置，但處理方式一致

情況二#

示例：LL

【特點】叔叔結點為黑色，衝突發生在 LL [兩個紅色結點在 L 和 LL]
【策略】
- 先使用 AVL 樹的旋轉調整策略：LL [示例]、LR、RL、RR
- 再修改三元組的顏色：紅色上浮 [紅黑黑] or 紅色下沉 [黑紅紅]
【分析】圖中 <LL 型失衡>，哪些結點是確定 [存在 + 顏色] 的？哪些是特例？
- 確定 [藍框框定]
  - LL 型 → 10、15
  - 情況二 → 25
  - 15 是紅色 → 20
  - 每條路徑黑色結點數量相同 [2 個] && 10、15 是紅色 → 5、13、19
  - [PS] 4 個黑色結點都是 NIL 也行
- 特例
  - 17
    - 可紅
    - 可無、可黑 [但不可包括在圖中，否則不滿足 5th 條件]
【圖示】大右旋 + 紅色上浮 / 下沉
- LL 型經大右旋後，黑色結點數量變化導致不平衡👉使用 [紅色上浮 / 下沉] 調整
[PS]
- 針對兩個紅色結點的旋轉，不影響每條路徑上的黑色結點數量
  - 對於小左旋、小右旋
  - 舉例：[原圖假設] 抓著 15 號結點小右旋
  - 所以小旋不會影響平衡
- ❗ 插入結點x的位置是回溯調整的中間結果，並不是直接插入後的樣子
- 包含 4 種小情況：LL、LR、RL、RR

刪除調整#

[目標] 解決雙黑情況

兩大類情況：兄弟結點為黑色 [2 + 2 + 2 種小情況]、兄弟結點為紅色 [特殊情況]

情況一#

示例：雙黑子結點在右側

【特點】雙重黑結點 x 的兄弟結點是黑色，兄弟結點的兩個子結點也是黑色
【策略】父結點增加 1 重黑，雙重黑結點與兄弟結點減少 1 重黑
[PS] 95 是回溯過來的 [看問題的格局要大]

情況二#

示例：RL

[注意觀察雙黑結點 x 的位置，關注 38 為根結點的子樹]
【特點】兄弟結點在右側 + 兄弟結點的左子結點是紅色，且右子結點一定是黑色 [否則判斷為 RR 型，見後]
【策略】小右旋，原兄弟結點改成紅色，新兄弟結點改成黑色，轉變成 RR 型 [見情況三]
【分析】哪些結點的顏色是確定的？[小右旋部分]
- [參照原圖，藍框框定為確定顏色]
- RL 型 → 72、51、85
- 根為 38 的子樹的每條路徑黑色結點數量相同 [2 個] && 51 是紅色 → 48、64

情況三#

示例：RR

[注意觀察雙黑結點 x 的位置，關注 38 為根結點的子樹]
【特點】兄弟結點在右側 + 其右子結點是紅色 [左子結點不做要求]
【策略】大左旋，新根結點等於原根結點 [雙黑結點的父結點] 的顏色，兩個新的子結點改為黑色，雙黑結點減少 1 重黑 [此順序無講究]
【分析】哪些結點的顏色是確定的？
- [參照原圖，藍框框定為確定顏色]
- RR 型 → 28、 51、72
- 每條路徑黑色結點數量相同 [≈2 個，38 不確定] && 72 是紅色 → 64、85
- [PS] 38、48 不確定
【思考 1】顏色修改策略
- 首先因為48有可能是紅色，為了避免可能的衝突 ❗，只能將 38 改為黑色
- 接下來，為了保證局部子樹的黑色結點數量在調整前、後相等
- ① [2 個] 如果 38 本來是紅色 → 51 改為紅色，72 改為黑色
- ② [3 個] 如果 38 本來是黑色 → 72 改為黑色
- 【通用方式】新根結點等於原根的顏色，新的子結點都改為黑色
  - 黑紅紅👉紅黑黑
  - (或者)
  - 黑黑紅👉黑黑黑
【思考 2】為什麼要通過左旋解決雙黑？
- 大左旋後，可以讓雙黑所在路徑上多一個黑結點 [51 的加入]，所以雙黑可以減一
  - 否則，平白無故的給雙黑減一，在哪裡可以保證給路徑上黑色結點數量加一呢

情況二、三小結

情況二：RL、LR；情況三：RR、LL
雙重黑結點的兄弟結點是黑色，且兄弟結點中有紅色子結點
- RR[兄弟結點在右側 ➕ 其右子結點是紅色]
  - 大左旋，新根改成原根的顏色，新根的兩個子結點改成黑色
- RL[兄弟結點在右側 ➕ 其左子結點是紅色，且右子結點一定是黑色]
  - 小右旋，原兄弟結點改成紅色，新兄弟結點改成黑色，再進行 RR 策略
- LL、LR：類同 RR、RL
優先級：RR > RL，LL > LR

特殊情況#

【特點】雙黑結點的兄弟結點是紅色
【策略】抓著雙黑結點的父結點，向雙黑結點旋轉，原根結點改為紅色，新根結點改為黑色
【圖示】大左旋 + 原 / 新根結點換色
- 藍框是確定顏色的結點，如何確定的？
  - 特殊情況 → 雙黑結點、兄弟結點
  - 4th 條件 && 兄弟結點是紅色 → 父結點
  - 5th 條件 && 兄弟結點是紅色 → 兄弟結點的子結點 [再往後黑色結點位置不一定要連續]
【轉換後】站在原根結點往下看，做刪除調整
- 此時，雙重結點的兄弟結點一定是黑色，即可轉到情況一、二、三

代碼演示#

插入調整#

根結點的手動染黑
- 保證 2nd 條件：根結點為黑色
- 什麼情況下，根結點會為紅色
  - 插入的第一個結點 [插入的結點為紅色]
  - 情況一的紅色上浮
  - 情況二的紅色上浮 [紅色下沉則不會影響]
- ❗ 只有手動染黑操作，會增加路徑上黑色結點的數量
  - 在根結點處發生大旋轉操作時，根結點會變成紅結點，此時手動染黑生效
- 通過代碼封裝處理：insert = __insert + 染黑
❓ 情況一的偷懶操作對回溯時的調整有沒有影響？
- 不會對下面的路徑產生衝突
- 不影響路徑的黑色結點數量
- 可能會導致上層結點發生衝突
  - 但本身就是隨機操作，當紅黑樹到了一定規模時，損耗可忽略不計
❓ 紅色下沉和紅色上浮的區別：各有各的好，都有衝突的可能
- 紅色下沉：容易和新插入的結點產生衝突
- 紅色上浮：容易和父結點產生衝突
  - [PS] 紅黑樹很大的時候，紅色結點很難上浮
❓ AVL 樹與紅黑樹
- AVL 樹比紅黑樹更平衡
- 紅黑樹調整的代價低於 AVL 樹
  - 紅黑樹約一半的調整都可以通過染色解決 [情況一]
- 適合動態插入和刪除結點，而查找可能稍遜於 AVL
[PS]
- 插入調整，發生在遞歸的回溯階段
- 插入調整的代碼中，使用 goto 語句，減少了代碼量；使用函數封裝應該更標準
[結果示例]

刪除調整#

在插入調整代碼的基礎上增加
刪除調整情況分為【無雙黑子結點】+【有雙黑子結點 [特殊情況 + 三種情況 (兄弟結點無 / 有紅孩子 <LR、LL、RL、RR>)]】
情況二、三，記得解決雙黑問題，順序無講究
進行 LR / RL 類型判斷的時候，不能直接判斷 LL 子樹是否為黑色
- 可能是黑色，也可能是雙重黑
- [雙重黑] 因為 LL 可能是 NIL 結點，而 NIL 結點在內存中是共用的，其顏色可能是雙重黑
- 【判斷轉變】判斷 LL 子樹是黑色 👉不是紅色
main 函數添加刪除操作
[結果示例]
- 演示了三種情況，結果見列表
- NIL 在內存中是共用的，可能都是雙重黑