紅黑樹 C 語言完整實現：插入、刪除、旋轉與驗證測試

紅黑樹五大性質

1. 節點非紅即黑。
2. 根節點為黑。
3. 葉節點（NIL）為黑。
4. 紅節點的子節點必為黑（無雙紅）。
5. 任一節點到所有後代葉節點的路徑含相同數目的黑節點（黑高一致）。

數據結構定義

#define RED 1\
#define BLACK 2\
\
struct Node {\
    Node *ch[2], *p;\
    int key, color;\
    Node() : ch{nullptr, nullptr}, p(nullptr), key(0), color(RED) {}\
};\
\
struct Tree {\
    Node *head, *nil;\
    Tree() { nil = new Node(); head = nil; nil->color = BLACK; }\
    // 方法聲明...\
};

• ch[0] 左子，ch[1] 右子。
• nil 哨兵節點統一表示所有葉子，簡化邊界判斷。
• 構造函數初始化 head=nil、nil->color=BLACK。

核心操作實現

1. 旋轉 rotate(t, c)

void rotate(Node *t, int c) {  // c=0 左旋, 1 右旋\
    Node *&pt = (t->p == nil) ? head : t->p->ch[t->p->ch[1] == t];\
    Node *y = t->ch[c^1];\
    t->ch[c^1] = y->ch[c];\
    y->ch[c]->p = t;\
    y->ch[c] = t;\
    y->p = t->p;\
    t->p = y;\
    pt = y;\
}

• c^1 取反方向：左旋操作右子，右旋操作左子。
• pt 為父節點指向 t 的指針引用，旋轉後直接指向新根 y，統一處理根與非根情況。

2. 插入修復 insert_fixup

void insert_fixup(Node *t) {\
    while (t->p->color == RED) {\
        Node *p = t->p, *g = p->p;\
        int pa = (g->ch[1] == p), ta = (p->ch[1] == t);\
        Node *u = g->ch[pa^1];  // 叔叔\
        if (u->color == RED) {  // Case 1: 叔叔紅\
            g->color = RED; p->color = u->color = BLACK;\
            t = g;\
        } else {\
            if (ta != pa) { rotate(p, ta^1); swap(t, p); ta = pa; }  // Case 2: 折線→直線\
            g->color = RED; p->color = BLACK;  // Case 3: 直線變色+旋轉\
            rotate(g, pa^1);\
        }\
    }\
    head->color = BLACK;\
}

• 三種情況標準教科書邏輯：變色上浮、折線轉直線、直線旋轉。
• swap(t, p) 交換指針變量，使 t 指向父節點，便於後續統一處理。

3. 刪除修復 remove_fixup

void remove_fixup(Node *t) {\
    while (t != head && t->color == BLACK) {\
        Node *p = t->p; int ta = (p->ch[1] == t);\
        Node *w = p->ch[ta^1];  // 兄弟\
        if (w->color == RED) { w->color = BLACK; p->color = RED; rotate(p, ta); w = p->ch[ta^1]; }\
        if (w->ch[0]->color == BLACK && w->ch[1]->color == BLACK) {\
            w->color = RED; t = p;  // Case 2: 兄弟雙黑，上推\
        } else {\
            if (w->ch[ta^1]->color == BLACK) {\
                w->ch[ta]->color = BLACK; w->color = RED; rotate(w, ta^1); w = p->ch[ta^1];  // Case 3\
            }\
            w->color = p->color; p->color = BLACK; w->ch[ta^1]->color = BLACK; rotate(p, ta); t = head;  // Case 4\
        }\
    }\
    t->color = BLACK;\
}

• 四種情況處理「雙黑」問題：兄弟紅→變色旋轉轉 Case 2/3/4；兄弟黑雙黑侄→變色上推；兄弟黑遠侄紅→轉 Case 4；兄弟黑遠侄紅→變色旋轉結束。

4. 後繼節點 successor

Node *successor(Node *t) {\
    if (t->ch[1] != nil) {\
        Node *p = t->ch[1]; while (p->ch[0] != nil) p = p->ch[0]; return p;\
    } else {\
        Node *p = t->p; while (p != nil && p->p->ch[1] == p) p = p->p; return p;\
    }\
}

測試驗證

int main() {\
    Tree tre;\
    for (int i = 0; i < 100; ++i) tre.insert(rand());\
    tre.out();  // 中序遍歷輸出黑高\
    for (int i = 0; i < 99; ++i) tre.remove(re[i]);\
    tre.out();\
}

out() 通過中序遍歷輸出每條路徑的黑節點數，驗證性質 5。運行無 bug 輸出說明插入刪除邏輯正確。

代碼亮點與工程價值

1. 哨兵節點統一邊界：nil 替代 NULL，消除大量空指針判斷。
2. 方向參數化：c/ta/pa 以 0/1 表示左右，旋轉、插入、刪除邏輯高度復用，代碼極度精簡。
3. 引用別名 pt：Node *&pt 統一根/非根旋轉接回邏輯。
4. 調試檢查：dfs 中檢查 ch[i]->p == t 確保父指針一致性。

這份實現展示了紅黑樹教科書級算法向工程代碼轉化的典範：正確性、簡潔性、可維護性兼備，是 C/C++ 開發者研究平衡樹實現的優秀參考。