紅黑樹算法層層剖析與逐步實現：從旋轉到插入修復完整推導

本文參考《算法導論》第二版與經典論文，結合作者手繪十張推導圖，將紅黑樹插入修復算法拆解為十個微步驟，實現「一步一圖一代碼」的教學目標。讀完你將能從零手寫出完整紅黑樹。

核心口訣：五大性質合為一

(1) 紅黑  (2) 黑  (3) 黑  (4&5) 紅→黑 黑

牢記此口訣，所有修復操作的終極目的只有一個：不違背五大性質。

一、 左旋與右旋：結構調整的原子操作

左旋以x → right[y]為支軸，使y上升為新根，x成為y左孩子，y原左孩子轉為x右孩子。右旋對稱。均為O(1)指標重接。

LEFT-ROTATE 偽代碼（算法導論版）

LEFT-ROTATE(T, x)
1  y ← right[x]                    // 設 y
2  right[x] ← left[y]              // y的左孩子 → x的右孩子
3  if left[y] ≠ nil[T]
4      then p[left[y]] ← x         // 更新父指標
5  p[y] ← p[x]                     // y 繼承 x 的父節點
6  if p[x] = nil[T]
7      then root[T] ← y            // x 是根 → y 成為新根
8  else if x = left[p[x]]
9      then left[p[x]] ← y
10     else right[p[x]] ← y
11 left[y] ← x                     // x 成為 y 左孩子
12 p[x] ← y

二、 區分兩類操作：修改 vs 修復

• 修改操作：RB-INSERT(T, z)、RB-DELETE(T, z) —— 純BST插入/刪除，不關心平衡。
• 修復操作：RB-INSERT-FIXUP(T, z)、RB-DELETE-FIXUP(T, x) —— 專職恢復五大性質，通過「變色+旋轉」完成。

混淆二者是初學者最大誤區，請務必劃清界限。

三、 RB-INSERT 主流程

RB-INSERT(T, z)
1  y ← nil[T]
2  x ← root[T]
3  while x ≠ nil[T]          // 尋找插入位置
4      do y ← x
5         if key[z] < key[x] then x ← left[x]
6         else x ← right[x]
7  p[z] ← y                   // y 為 z 父節點
8  if y = nil[T] then root[T] ← z
9  else if key[z] < key[y] then left[y] ← z
10     else right[y] ← z
11 left[z] ← nil[T]
12 right[z] ← nil[T]
13 color[z] ← RED             // 關鍵：新節點著紅
14 RB-INSERT-FIXUP(T, z)      // 進入修復流程

第13行著紅是為什麼？因著黑會立即增加黑高，破壞性質5難以局部修復；著紅最多違背性質4（紅不相鄰），修復路徑更可控。

四、 RB-INSERT-FIXUP 三大情況完整拆解

循環不變量：z為紅，且只有z與其父可能同時為紅（違背性質4）。

情況1：叔節點 y 為紅

動作：父、叔變黑；祖父變紅；z ← 祖父繼續向上檢查。
本質：將「紅紅衝突」上推一層，保持黑高不變。

情況2：叔節點為黑，且 z 為右孩子（LR型）

動作：對父節點左旋 → 轉化為情況3。
關鍵：旋轉後z指標下移一層，成為原父節點位置。

情況3：叔節點為黑，且 z 為左孩子（LL型）

動作：父變黑、祖父變紅、對祖父右旋 → 修復結束。
本質：局部重構，紅紅衝突消除，黑高平衡恢復。

五、 手繪十張推導圖對照表

建議讀者打印十張圖，對照偽代碼逐行推演，再動手用C/C++實現RB_INSERT_FIXUP。下篇將帶來完整C語言源碼與刪除修復深度解析。