紅黑樹圖解教程：一步一圖一代碼，徹底搞懂插入與刪除修復

本文承接前三篇紅黑樹系列，採用「宏觀總結 → 統一符號 → 分情況圖解 → 代碼對照」四層結構，誓要讓你對紅黑樹插入/刪除修復的每一種情況都能看到圖、讀懂碼、寫出來。

前置共識：五大性質與操作分層

（同前文，此處不贅述）關鍵區分：
修改層：RB-INSERT/RB-DELETE（純BST邏輯）
修復層：RB-INSERT-FIXUP/RB-DELETE-FIXUP（變色+旋轉）

統一符號約定

一、 插入修復五種情況（遞歸/迭代統一）

情形1：N 為根節點（無父節點）

void insert_case1(node n) {
    if (n->parent == NULL) n->color = BLACK;
    else insert_case2(n);
}

情形2：父節點 P 為黑

void insert_case2(node n) {
    if (n->parent->color == BLACK) return;  // 已滿足性質
    else insert_case3(n);
}

情形3：父 P 紅、叔 U 紅

void insert_case3(node n) {
    if (uncle(n) && uncle(n)->color == RED) {
        n->parent->color = BLACK;
        uncle(n)->color = BLACK;
        grandparent(n)->color = RED;
        insert_case1(grandparent(n));  // 遞歸向上
    } else insert_case4(n);
}

情形4：父紅、叔黑，N 為右孩子且 P 為左孩子（或鏡像）

void insert_case4(node n) {
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
        rotate_left(n->parent);
        n = n->left;
    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
        rotate_right(n->parent);
        n = n->right;
    }
    insert_case5(n);  // 必進入情形5
}

情形5：父紅、叔黑，N 為左孩子且 P 為左孩子（或鏡像右右）

void insert_case5(node n) {
    n->parent->color = BLACK;
    grandparent(n)->color = RED;
    if (n == n->parent->left && n->parent == grandparent(n)->left)
        rotate_right(grandparent(n));
    else
        rotate_left(grandparent(n));  // 鏡像情況
}

二、 刪除修復四種情況

符號：x為「雙重黑」傳遞節點，w = sibling(x)為兄弟節點。

情況1：兄弟 w 為紅

動作：父變紅、w變黑、對父旋轉（方向視x是左/右孩子）→ 轉化為情況2/3/4。
本質：紅兄弟旋轉後變黑，為後續處理創造黑兄弟前提。

情況2：兄弟 w 為黑，且 w 兩個孩子均為黑

動作：w變紅、x ← 父節點向上傳遞雙重黑。
本質：從兄弟「借」一個黑高給父路徑，自己變紅補償。

情況3：兄弟 w 為黑，w左孩子紅、右孩子黑

動作：w左孩子變黑、w變紅、對w右旋 → 轉化為情況4。

情況4：兄弟 w 為黑，w右孩子紅

動作：w繼承父顏色、父變黑、w右孩子變黑、對父左旋 → 修復結束。
本質：一次旋轉+三次變色，完美平衡黑高，雙重黑消除。

三、 學習建議

1. 打印本文所有圖片，對照代碼逐行單步模擬。
2. 用C語言實現insert_case1~5與delete_case1~4，編譯運行測試隨機序列。
3. 對照《算法導論》第13.3-13.4節，核對偽代碼細節差異。

掌握這九種情況（插入5+刪除4），紅黑樹核心算法便真正收入囊中。