摘要訊息 : 應用最多的平衡樹.

0. 前言

在《【資料結構】樹——AVL 樹》, 我們介紹了搜尋時間為 \Theta(\log {n}) 的平衡樹. AVL 樹的高度是二元搜尋樹中最平衡的樹之一. 然而, AVL 樹移除操作中, L₁ 型不平衡, R₁ 型不平衡和 L_-1 型不平衡的平衡調整操作可能需要一直調整至根節點才停止. 這樣的調整操作過於複雜, 我們希望像插入操作那樣, 進行雙旋轉就可以使得樹恢復平衡.

Tip : 為了避免顏色遮蓋, 本文圖像中所有黑色節點將被灰色節點所替代. 對於那些顏色不確定的節點, 將被設為無顏色, 連向這些節點的連線將是灰色的.

1. 定義

定義 1. 我們對二元搜尋樹 \mathcal {T} 中所有節點進行染色, 顏色僅限於紅色和黑色. 若 \mathcal {T} 滿足

• 從根節點到葉子節點的不同路徑上, 黑色節點的數量都相同;
• 從根節點到葉子節點的路徑上, 不存在連續兩個紅色節點, 即紅色節點的子節點仍然是紅色的,

那麼我們稱 \mathcal {T} 為紅-黑樹 (red-black tree, 簡稱為紅黑樹).

定義 1'. 我們對二元搜尋樹 \mathcal {T} 中所有子節點指向型標記 (參考《【資料結構】樹》定義 1) 進行染色, 顏色僅限於紅色和黑色. 若 \mathcal {T} 滿足

• 從根節點到葉子節點的不同路徑上, 黑色子節點指向型標記的數量都相同;
• 從根節點到葉子節點的路徑上, 不存在連續兩個紅色子節點指向型, 即指向某個節點的指向型標記是紅色的, 而該節點指向子節點的指向型標記仍然是紅色的,

那麼我們稱 \mathcal {T} 為紅-黑樹, 簡稱為紅黑樹.

定義 1 和定義 1' 實際上是等價的, 一個針對節點另一個針對指向型標記. 根據《【資料結構】樹》定義 13, 任意紅黑樹都是一棵平衡樹, 其平衡條件為 \displaystyle {B = \left \{ 任意路徑上的黑色節點都相同且不存在兩個連續紅色節點 \right \}}.

顯然地, 我們容易從定義 1 知道任意紅黑樹中, 以黑色節點為根節點的子樹也是一棵紅黑樹.

定義 2. 我們稱紅黑樹 \mathcal {T} 上任意路徑中黑色節點的數量為 \mathcal {T} 的階 (rank).

定義 3. 對於紅黑樹 \mathcal {T} 中那些存在子節點為空的節點, 為這些節點擴充一個不存在值的黑色節點, 我們稱為擴充節點 (expansion node), 並且稱 \mathcal {T} 為擴充後的紅黑樹 (expanded red-black tree).

需要注意的是, 事實上擴充節點並不存在, 而僅僅是理論上存在. 例如在 C++ 中, 它們都是 nullptr. 也就是說, 我們只是把空的子節點視為黑色, 並不是真的拿擴充節點替代空節點.

2. 性質

性質 1. 若紅黑樹 \mathcal {T} 不為空, 則新插入 \mathcal {T} 的節點一定是紅色的.

證明 :

由定義 1 可知, 對於一棵已經建構完成的紅黑樹 \mathcal {T}, 若新插入節點為黑色, 這將破壞 \mathcal {T} 每條路徑上的黑色節點平衡. 因此新插入 \mathcal {T} 的節點只能是紅色節點.

\blacksquare

性質 2. 紅黑樹中新插入節點的父節點必定是黑色的.

證明 :

由定義 1 可知, 一條路徑上不能出現連續兩個紅色節點, 結合性質 1 可以知道新插入節點, 即葉子節點的父節點必定為黑色節點.

\blacksquare

性質 3. 擴充後的紅黑樹中從根節點到兩個不同葉子節點的兩條路徑 P 和 Q 滿足 \displaystyle {s(P) \leq 2s(Q)}. 其中, s 是路徑長度.

證明 :

設擴充後的紅黑樹的階為 r. 由定義 3 可知, 擴充節點必定為黑色. 由定義 1 可知, 每一個紅色節點之後必定是一個黑色節點. 一條路徑上, 至多可以有 r 個紅色節點, 最少時一個紅色節點都沒有. 當一條路徑上的紅色節點數量為 r 時, 結合紅黑樹的階, 那麼這條路徑上共計會有 2r 個節點; 當一條路徑上一個紅色節點都沒有時, 那麼這條路徑上僅有 r 個節點, 且都是黑色的. 因此, 一個階為 r 的擴充紅黑樹中, 任意路徑長度的範圍在 [r, 2r]. 極端地, 當 s(P) = r 時, 由於 s(Q) \geq r, 故必定有 \displaystyle {s(P) = r \leq s(Q) \Rightarrow s(P) \leq s(Q)}; 當 s(P) = 2r 時, 由於 s(Q) \geq r, 故 2s(Q) \geq 2r, 因此 \displaystyle {s(P) = 2r \leq 2s(Q) \Rightarrow s(P) \leq 2s(Q)}.

綜上所述, 總有 s(P) \leq 2s(Q).

\blacksquare

性質 4. 設紅黑樹 \mathcal {T} 的高度為 h, 其共有 n 個節點, 階為 r, 則有

1. h \leq 2r;
2. n \geq 2^{r} - 1;
3. h \leq 2\log_{2}{(n + 1)}.

證明 :

由性質 3 可知, \mathcal {T}' 的階為 r, 因此任取一條路徑, 節點數量至多是 2r 個. 因此, h \leq 2r.

(1) \square

由於 \mathcal {T} 的階是 r, 因此紅黑樹至少有 r 層. 又因為紅黑樹必定是二元樹, 根據《【資料結構】樹——二元樹》性質 2, 因此 n \geq 2^{r} - 1.

(2) \square

由 (1) 可知, r \geq \frac {h}{2}; 由 (2) 可知, r \leq \log_{2}{(n + 1)}. 因此有 \frac {1}{2}h \leq \log_{2}{(n + 1)}, 即 h \leq 2\log_{2}{(n + 1)}.

(3)\square

\blacksquare

3. 搜尋

二元搜尋樹的搜尋演算法完全可以用於紅黑樹, 但是紅黑樹的高度並不像 AVL 樹那樣平衡, 所以理論上來說, AVL 樹的搜尋高度是最優的. 不過由性質 4 可以知道, 紅黑樹的搜尋時間複雜度和 AVL 樹是一樣的, 都是 \Theta(\log {n}), 空間複雜度也完全相同. 雖然在最壞的情況下, 紅黑樹的搜尋會比 AVL 樹要慢一些, 但是至少不會發生二元搜尋樹那種退化為 \Theta(n) 的極端情形.

4. 插入

和 AVL 樹類似, 由於都是二元搜尋樹, 所以紅黑樹的插入操作也是使用二元搜尋樹的插入操作, 如果紅黑樹的平衡被破壞, 那麼就進行調整. 性質 1 和性質 2 實際上是針對平衡調整之後的情況, 因為平衡調整之前的樹並不滿足定義 1, 也就不是一棵紅黑樹 (雖然所有的節點都是紅色或者黑色), 自然這兩個性質都不能被滿足.

我們首先討論樹為空的情形. 根據定義 1, 紅黑樹並沒有嚴格規定新插入的根節點應該是什麼顏色的. 從這個角度來說, 新插入的根節點既可以是紅色也可以是黑色的. 但是, 如果新插入的根節點是紅色的, 那麼當我們再次向紅黑樹中插入節點時, 根據性質 1, 這個節點必定也是紅色的. 此時, 結合性質 2, 我們就需要將根節點調整為黑色. 既然這樣, 我們就給紅黑樹劃定了一個潛規則 : 在樹為空的時候, 新插入的節點為黑色. 這也就是性質 1 的例外情形.

再來討論樹不為空的情形. 根據性質 1, 新插入的節點為紅色節點, 所以它可能引起插入節點處存在兩個連續的紅色節點, 這就導致紅黑樹的平衡被破壞, 需要進行調整. 設新插入的節點為 n, 其父節點為 p, 祖父節點 (父節點的父節點) 為 g, p 的兄弟節點 (g 的另外一個子節點) 為 b. 需要說明的是, 如果 b = \infty, 這個時候我們考慮擴充這棵紅黑樹, 那麼 b 應該是黑色的. 這樣, 我們根據插入節點所在的位置, 其父節點所在的位置和兄弟節點的顏色對不平衡類型進行分類 :

• LLb 型 : n 是 p 的左子節點, p 是 g 的左子節點, b 是黑色節點;
• LLr 型 : n 是 p 的左子節點, p 是 g 的左子節點, b 是紅色節點;
• LRb 型 : n 是 p 的左子節點, p 是 g 的右子節點, b 是黑色節點;
• LRr 型 : n 是 p 的左子節點, p 是 g 的右子節點, b 是紅色節點;
• RRb 型 : n 是 p 的右子節點, p 是 g 的右子節點, b 是黑色節點;
• RRr 型 : n 是 p 的右子節點, p 是 g 的右子節點, b 是紅色節點;
• RLb 型 : n 是 p 的右子節點, p 是 g 的左子節點, b 是黑色節點;
• RLr 型 : n 是 p 的右子節點, p 是 g 的左子節點, b 是紅色節點.

仔細觀察, 不難發現我們可以將不平衡類型分為 XYr 型或者 XYb 型. 其中, X 和 Y 可以是 L 或者 R. 對於 XYr 型不平衡, 我們只需要調整節點顏色不需要進行旋轉; 對於 XYb 型不平衡, 我們需要通過旋轉來調整.

在 XYr 型不平衡中, b 必定是紅色節點, 所以我們不再明確畫出. 那麼, XYr 型不平衡的四種情況如下所示 :

其中, g_{\mathrm {L}} 或者 g_{\mathrm {R}} 是以 b 為根節點的子樹. 我們首先將 g 的兩個子節點全部調整為黑色, 再考慮 g 是不是根節點. 如果 g 是根節點, 那麼調整到此為止, 此時所有路徑上的黑色節點都會增加一, 紅黑樹的階也會增加一; 如果 g 不是根節點, 那麼需要將 g 改為紅色節點. 這個時候, 我們還需要考慮 g 的父節點是否為紅色節點, 如果是的話, 平衡調整還需要繼續. 如果 g 的父節點是紅色節點, 那麼根據 g 的祖父節點必定為黑色節點. 此時, g 為紅色節點, g 的祖父節點 g' 是紅色節點, g 的曾祖父節點 g'' 是黑色節點. 這個時候, 需要根據對應的不平衡類型進行相應的處理. 如果 g'' 是根節點, 或者 g'' 在調整之後恢復了平衡, 那麼平衡調整到此為止; 否則, 平衡調整就要一直繼續, 甚至直到根節點. 雖然我們暫時還沒有介紹 XYb 型不平衡如何調整, 但是幸運的是, 如果遇到上溯時遇到 XYb 不平衡情形, 經過旋轉調整之後就不需要再上溯了. 因此, XYr 型不平衡的調整可能有 O(\log {n}) 次顏色改變至多兩次旋轉, 其時間複雜度為 O(\log {n}). 顯然, 不論是顏色改變還是旋轉, 所需要的輔助空間都和節點數量無關, 因此 XYr 型不平衡調整的空間複雜度為 \Theta(1).

比較 Figure 3 和 Figure 4, 我們發現唯一的不同就是 g 連向 b 的連線顏色從紅色變成了黑色, 也就是節點 b 變成了黑色節點. 然而, XYb 型不平衡不能僅僅通過調整顏色來恢復平衡, 還需要借助旋轉. LLb 型不平衡需要進行一次顏色調整和一次旋轉才能恢復平衡. 首先, 我們像 XYr 型不平衡那樣對節點顏色進行改變, 即將 p 改成黑色節點, g 改成紅色節點. 因為 b 本來就是黑色節點, 所以不需要改.

在經過顏色調整之後, 我們發現 g_{\mathrm {R}} 這條路徑上黑色節點少了一個, 所以還需要進行一次右旋轉保持黑色節點的平衡.

這樣, LLb 型不平衡調整就完成了. RRb 型不平衡和 LLb 型不平衡是對稱的, 首先進行相同的顏色調整, 然後對稱地進行左旋轉.

LRb 型不平衡需要進行雙旋轉還有一次顏色改變才能恢復平衡. 首先, 以 n 為中心進行左旋轉 :

然後按照 XYr 型不平衡的處理方法, 進行顏色調整 :

最後再以 n 為中心進行右旋轉 :

至此, LRb 型不平衡的調整就完成了. 類似地, RLb 型不平衡和 LRb 型不平衡是對稱的 :

我們注意到, LRb 型不平衡和 RLb 型不平衡中, 若 g 是根節點, 我們仍然將 g 的顏色改為紅色. 因為在經過旋轉調整之後, 新的根節點將是 n, 而不是 g.

總體來說, XYb 型不平衡只需要進行一次顏色改變以及至多兩次旋轉即可恢復平衡, 因此 XYb 型不平衡調整的時間複雜度和空間複雜度都為 \Theta(1). 然而需要指出的是, 在有 XYb 型不平衡之前, 紅黑樹很可能經過了 O(\log {n}) 次顏色調整. 因為 XYr 型不平衡需要一直上溯, 這期間如果一直遇到 XYr 型不平衡, 那麼就一直需要進行顏色調整, 直到遇到根節點或者 XYb 型不平衡才結束. 綜上所述, 紅黑樹的插入操作的時間複雜度為 O(\log {n}), 空間複雜度為 \Theta(1).

5. 移除

我們同樣使用二元搜尋樹的移除演算法在紅黑樹中移除元素, 如果移除操作引起了樹的不平衡, 那麼就進行調整. 從紅黑樹的定義來看, 移除紅色節點是不會引起不平衡的. 如果從紅黑樹中移除一個黑色節點, 那麼分為兩種情況. 一種是這個黑色節點有兩棵非空子樹, 另一種是這個黑色節點僅有一棵非空子樹或者這個黑色節點就是一個葉子節點. 如果黑色節點有兩棵非空子樹, 那麼我們不會真正移除這個黑色節點, 我們一般會選擇用左子樹中的最大元素或者右子樹中的最小元素來替換黑色節點中的元素. 接著, 真正被移除的節點是左子樹中最大元素對應的那個節點或者右子樹中最小元素對應的那個節點, 不妨記真正被移除的節點為 d. 如果 d 是紅色節點, 那麼紅黑樹的平衡也沒有被破壞. 對於其它情況, 移除一個黑色節點會導致對應路徑上的黑色節點數量減少一, 從而導致紅黑樹的不平衡.

同樣地, 我們對移除操作所導致的紅色樹不平衡情況進行劃分. 首先, 設真正被移除的節點為 n, 其父節點為 p, 兄弟節點 (p 的另外一個子節點) 為 b. 根據 n 所處的位置, 總體地, 將不平衡類型劃分為 L 型和 R 型. 其中, L 型表示 n 是 p 的左子節點, R 型表示 n 是 p 的右子節點. 為了繼續對不平衡類型進行細分, 我們需要討論 b 的存在型.

斷言 1. 被移除節點 n 的兄弟節點 b 必定存在.

證明 :

我們知道, n 必定是黑色的. 不論 n 的 p 節點是什麼顏色, 如果以 b 為根節點的子樹中不存在黑色節點, 那麼這棵樹不再符合紅黑樹的定義. 因此, 只有兩種可能 : b 是黑色節點或者 b 的兩棵子樹中各自都至少有一個黑色節點. 於是, b 必定存在.

\blacksquare

根據斷言 1, 既然 b 必定存在, 那麼我們可以根據 b 的顏色和 b 子節點中紅色節點的數量 (若子節點為空, 那麼考慮擴充紅黑樹, 此時擴充節點是黑色節點) 對不平衡類型繼續細分 :

• Lb 型不平衡 : n 是 p 的左子節點且 b 是黑色節點,
  • Lb0 型不平衡 : b 沒有紅色的子節點;
  • Lb1 型不平衡 : b 有一個紅色的子節點,
    • Lb1L 型不平衡 : b 的紅色子節點為左子節點;
    • LB1r 型不平衡 : b 的紅色子節點為右子節點;
  • LB2 型不平衡 : b 的兩個子節點都是紅色節點;
• Rb 型不平衡 : n 是 p 的右子節點且 b 是黑色節點,
  • Rb0 型不平衡 : b 沒有紅色的子節點;
  • Rb1 型不平衡 : b 有一個紅色的子節點,
    • Rb1L 型不平衡 : b 的紅色子節點為左子節點;
    • Rb1b 型不平衡 : b 的紅色子節點為右子節點;
  • RB2 型不平衡 : b 的兩個子節點都是紅色節點;
• Lr 型不平衡 : n 是 p 的左子節點且 b 是紅色節點,
  • Lr0 型不平衡 : b 的左子節點 m 沒有紅色子節點;
  • Lr1 型不平衡 : b 的左子節點 m 有一個紅色子節點,
    • Lr1L 型不平衡 : m 的左子節點是紅色節點;
    • Lr1R 型不平衡 : m 的右子節點是紅色節點;
  • Lr2 型不平衡 : b 的左子節點 m 有兩個紅色子節點;

• Rr 型不平衡 : n 是 p 的右子節點且 b 是紅色節點,
  • Rr0 型不平衡 : b 的右子節點 m 沒有紅色子節點;
  • Rr1 型不平衡 : b 的右子節點 m 有一個紅色子節點,
    • Rr1L 型不平衡 : m 的左子節點是紅色節點;
    • Rr1R 型不平衡 : m 的右子節點是紅色節點;
  • Rr2 型不平衡 : b 的右子節點 m 有兩個紅色子節點.

這裡說明一下在 Lr 型不平衡和 Rr 型不平衡中, b 的子節點為什麼必定存在. 由於 b 是紅色節點, 又根據斷言 1, 以 b 為根節點的兩棵子樹都至少存在一個黑色節點. 也就是說, b 的左子樹和右子樹中至少存在一個節點. 另外, 由於 b 是紅色節點, 根據紅黑樹的定義, 其子節點必定是黑色節點, p 也是黑色節點. 我們約定, 當節點 n 被移除之後, p 的某個子樹我們會用 p_{\mathrm {L}} 或者 p_{\mathrm {R}} 來替代.

我們首先討論 Lb0 型和 Rb0 型不平衡, 這兩種不平衡的調整方式是一樣的. 當 n 被移除之後, 假設原來以 n 為根節點的子樹變成了以 p_{\mathrm {L}} 或者 p_{\mathrm {R}} 為根節點的子樹.

這個時候, 以 p_{\mathrm {L}} 或者 p_{\mathrm {R}} 為子樹的階就會減少一. 在 Lb0 型不平衡中, p 右子樹中的黑色節點會比左子樹中的黑色節點多一個; 在 Rb0 型不平衡中, p 左子樹中的黑色節點會比右子樹中的黑色節點多一個. 這導致了以 p 為根節點的子樹的不平衡. 這個時候, 我們將 b 改變為紅色節點. 另外, 如果 p 不是黑色節點, 那麼就把 p 改為黑色節點.

在顏色調整完成之後, 以 p 為根節點的子樹的黑色節點數量就會減少一. 如果 p 不是根節點, 這又會導致 p 的父節點的兩個子節點黑色節點數量不同. 因此, 當 p 不是根節點的時候, 就要像插入操作的 XYr 型不平衡那樣上溯重新劃分不平衡情況, 然後繼續進行調整, 直到紅黑樹恢復平衡或者遇到根節點為止. 設 p 的父節點為 g, 兄弟節點 (g 的另一個子節點) 為 b', 接著上溯過程中, 我們根據 p, g, b' 甚至 b' 子節點中紅色節點的數量重新劃分不平衡情況, 然後進行調整. 雖然我們暫時還沒有介紹其它不平衡情況如何調整, 不過幸運的是, 如果上溯過程中遇到其它不平衡情況, 我們至多進行三次旋轉即可讓紅黑樹恢復平衡. 因此, Xb0 型不平衡調整的時間複雜度為 O(\log {n}).

對於 Rb1L 型不平衡和 Lb1R 型不平衡, 它們是對稱的, 調整的方法類似. 當我們將 n 移除之後, 有

此時, p_{\mathrm {L}} 和 p_{\mathrm {R}} 和以 b 為根節點的子樹相比, 少了一個黑色節點. 我們容易想到, 對於 Lb1R 型不平衡, 進行左旋轉之後就可以保持左側路徑上的黑色節點平衡; 類似地, 對於 Rb1L 型不平衡, 進行右旋轉可以讓右側路徑上的黑色節點保持平衡.

但是, 我們忽略了 p 的顏色. 如果 p 是黑色節點, 那麼這將導致 b_{\mathrm {R}} 或者 b_{\mathrm {L}} 這條路徑上少了一個黑色節點. 因此, 我們可以將 b 的顏色調整為 p 的顏色, 然後將 p 和 b_{\mathrm {R}} 中的根節點及 b_{\mathrm {L}} 中的根節點都調整為黑色節點. 這樣, 紅黑樹的平衡就恢復了.

對於 Lb1L 型不平衡和 Rb1R 型不平衡, 我們都需要分解紅色的那個節點, 然後通過一次顏色調整和雙旋轉來恢復平衡.

以 c 為中心, Lb1L 型不平衡進行右旋轉, Rb1R 型不平衡進行左旋轉.

由於我們不知道 p 的具體顏色, 也不知道 p_{\mathrm {L}} 根節點是什麼顏色. 為了避免旋轉之後還是不平衡, 所以我們選擇將 c 的顏色改為 p 的顏色, 然後將 p 改為黑色節點.

最後, 以 c 為中心, Lb1L 型不平衡進行左旋轉, Rb1R 型不平衡進行右旋轉. 這樣, c 右子樹中的黑色節點數量就增加了一個, 樹恢復了平衡.

Lr0 型不平衡和 Rr0 型不平衡需要經過一次旋轉和一次顏色調整就可以恢復平衡. 總體的方法也是讓少了一個黑色節點的那條路徑通過旋轉和顏色調整再增加一個黑色節點以保持平衡.

接著以 b 為中心, Lr0 型不平衡進行左旋轉, Rr0 型不平衡進行右旋轉.

在旋轉之後, 我們再將 b 更改為黑色節點, 以避免 b 為根節點時, 顏色不符合潛規則; 或者避免 b 及其兄弟節點的黑色節點數量不平衡. 這樣, 樹就恢復了平衡.

Lr1R 型不平衡和 Rr1L 型不平衡則需要通過雙旋轉和一次顏色調整來恢復平衡.

首先, 以 m 為中心, Lr1R 型不平衡進行右旋轉, Rr1L 型不平衡進行左旋轉.

顯然, 旋轉之後出現了兩個連續的紅色節點. 為了避免 Lr1R 型不平衡中的 m_{\mathrm {R}} 和 Rr1L 型不平衡中的 m_{\mathrm {L}} 中的黑色節點數量減少, 所以我們將這兩棵子樹的根節點改為黑色節點.

接著, 以 m 為中心, Lr1R 型不平衡進行左旋轉, Rr1L 型不平衡進行右旋轉. 最終, 樹恢復平衡.

Lr1L 型不平衡和 Lr2 型不平衡的調整方式完全相同. 對稱地, Rr1R 型不平衡和 Rr2 型不平衡的調整方式也完全相同. 到目前為止, 無論是 AVL 樹還是紅黑樹, 如果不算入上溯調整的次數, 那麼一個不平衡調整至多使用了雙旋轉, 有些單旋轉即可恢復平衡. 不過通過 Figure 9-3 和 Figure 9-4, 不論是 Lr1L 型不平衡還是 Lr2 型不平衡, 亦或是 Rr1R 型不平衡和 Rr2 型不平衡, 是無法通過單旋轉恢復的. 因為不論以 b 為中心進行單旋轉還是以 m 為中心進行單旋轉, 我們都無法補足因為 n 移除而導致對應子樹中缺少的那個黑色節點. 因此, 我們考慮使用雙旋轉. 根據前面的經驗, 雙旋轉一般都是以 m 為中心旋轉兩次, 使得 m 可以成為新的根節點. 在第一次旋轉之後, 進行一次顏色調整, 再進行一次旋轉, 即可恢復平衡. 以 Lr1L 型不平衡為例, 以 m 為中心, 先進行右旋轉, 得到

根據之前的經驗, 接下來我們應該改變節點顏色. 由於 m 是黑色節點, b 是紅色節點, 一種選項是把 m 改為紅色節點, 然後把 m_{\mathrm {L}} 的根節點和 b 改為黑色節點. 但是顯然這樣是不可行的, 因為 m 不能是紅色的. 可以回顧一下前面所有的平衡調整, 新的根節點都是黑色的. 而且如果 m 再一次旋轉之後成為了整棵樹的根節點, 就更不能把 m 調整為紅色. 那麼保持 m 為黑色, 將 m_{\mathrm {L}} 的根節點和 b 也改為黑色節點. 這樣, p 的右子樹中黑色節點數量會比左子樹多兩個. 即使再以 m 為中心進行一次左旋轉, 也調整不回來. 綜上所述, 雙旋轉也不適用. Lr2 型不平衡, Rr1R 型不平衡和 Rr2 型不平衡都會有類似的情況.

既然結合簡單顏色調整的單旋轉和雙旋轉都無法使得 Lr1L 型不平衡, Lr2 型不平衡, Rr1R 型不平衡和 Rr2 型不平衡獲得恢復, 那麼只能考慮再多一次旋轉, 也就是三旋轉. 所謂三旋轉, 也可以看成是一次單旋轉結合一次雙旋轉. 首先, 我們分解 m 中那個紅色節點為 c 及其左子節點 c_{\mathrm {L}} 和右子節點 c_{\mathrm {R}}. 由於 Lr2 型不平衡和 Rr2 型不平衡中, 兩個子節點都是紅色節點, 所以對於 Lr2 型不平衡我們和 Lr1L 型不平衡一樣分解 m 的左子節點, 對於 Rr2 型不平衡我們和 Rr1R 型不平衡一樣分解 m 的右子節點.

接下來以 c 為中心, 進行單旋轉. 具體地, Lr1L 型不平衡和 Lr2 型不平衡進行右旋轉, Rr1R 型不平衡和 Rr2 型不平衡進行左旋轉.

既然接下來還要進行雙旋轉, 因此 c 會成為新的子樹根節點, 所以要把 c 的顏色改為黑色.

接下來要通過雙旋轉將 c 調整至新的子樹根節點. 具體地, 先以 c 為中心, Lr1L 型不平衡和 Lr2 型不平衡進行右旋轉, Rr1R 型不平衡和 Rr2 型不平衡進行左旋轉.

然後以 c 為中心, Lr1L 型不平衡和 Lr2 型不平衡進行左旋轉, Rr1R 型不平衡和 Rr2 型不平衡進行右旋轉. 最終, 樹恢復平衡.

除了 Lb0 型不平衡和 Rb0 型不平衡可能需要上溯之外, 其它類型的不平衡都是通過旋轉和顏色調整來恢復樹的平衡. 因此, 紅黑樹移除操作的時間複雜度為 O(\log {n}), 空間複雜度為 \Theta(1).

6. 和 AVL 樹的比較

在第 3 節中, 我們已經說過, 在最壞情況下 AVL 樹中的搜尋操作會比紅黑樹中快. 除此之外, 根據 AVL 樹和紅黑樹各自的定義, AVL 樹的平衡性遠比紅黑樹要高. 紅黑樹對左右子樹的高度並沒有嚴格的要求, 只需要每條路徑上的黑色節點保持相同即可. 因此, 從樹的高度來說, AVL 樹通常會比紅黑樹要低一些. 這從另外一個層面說明了 AVL 搜尋的高效性. 但是在很多實際應用中, 通常並不會採用 AVL 樹, 而是採用紅黑樹. 例如 C++ 標準樣板程式庫中的有序關聯容器 std::map, std::multimap, std::set 和 std::multiset 低層資料結構都是紅黑樹, 而不是搜尋效能更高的 AVL 樹. 這是因為紅黑樹在保持平衡這一方面要比 AVL 樹要簡單. AVL 樹的旋轉調整有時候要持續到根節點才停止, 而紅黑樹的顏色調整操作肯定比旋轉要快一些. 另一方面, 紅黑樹旋轉的次數要比 AVL 少, 這也和 AVL 樹的旋轉調整有時候要持續到根節點有關, 但是紅黑樹的旋轉操作至多是三次即可讓樹恢復平衡. 所以結合插入, 移除和搜尋這三者的綜合效能, 紅黑樹通常高效一點點 (當然, 這是前人通過不斷實驗得出的經驗, 數學上無法嚴格證明).

從多執行緒的角度來說, 紅黑樹在移除操作所需要鎖定的節點數量通常會比 AVL 樹少, 這也可以從上一段的討論中輕易得到. 從快取的角度來說, 紅黑樹的移除操作絕大多數情況下可以利用快取提升效能. 因為紅黑樹只有 Lb0 型不平衡和 Rb0 型不平衡需要上溯檢查, 而 AVL 樹只有 L₀ 型不平衡和 R₀ 型不平衡不需要上溯檢查. 這裡我們可以斷言, AVL 樹存取記憶體的次數會比紅黑樹多.

因此, 一棵樹如果在建構之後經常需要移除節點, 那麼應該優先選用紅黑樹; 如果在建構之後幾乎不進行移除操作, 而經常需要進行搜尋操作, 那麼應該優先選用 AVL 樹.

7. 實作

我自己用 C++ 實作了紅黑樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/red_black_tree.hpp, 大家可以參考後自行實作.