算法導論：紅黑樹刪除操作完整解析與 C 語言實現

紅黑樹五大性質回顧

紅黑樹作為自平衡二叉搜尋樹，維持以下五大性質：

1. 每個節點非紅即黑
2. 根節點為黑色
3. 所有葉子節點（NIL）為黑色
4. 紅色節點的兩個子節點必為黑色
5. 任一節點到其所有後代葉子節點的路徑，包含相同數目的黑色節點

刪除操作時間複雜度同為 O(log₂N)，但處理邏輯較插入複雜。

刪除流程三大情況

假設需刪除節點 D，分三種情況處理：

情況 1：D 的左子節點為葉子，右子節點無限制

用右子節點取代 D 的位置。若 D 為紅色，性質未破壞；若 D 為黑色，需進一步調整。

情況 2：D 的右子節點為葉子，左子節點非葉子

用左子節點取代 D 的位置。同樣，D 為紅色無需調整，黑色則需調整。

情況 3：D 的左右子節點均非葉子

找到 D 的後繼節點 S，將 S 的 key 值賦給 D，再刪除 S 並用 S 的右子節點取代 S 位置。實際被刪除的是 S。若 S 為紅色無需調整，黑色則需調整。

結論：僅當實際被刪除的節點為黑色時，才可能破壞紅黑樹性質，需進入調整階段。

調整過程四大案例（前提：參照節點 N 為父節點 P 的左子節點）

案例 1：兄弟節點 B 為紅色

將 P 改紅、B 改黑，以 P 為支點左旋 → 轉化為案例 2、3 或 4。

案例 2：B 為黑色，且 B 的兩個子節點均為黑色

將 B 改紅 → 調整結束，重新判斷前提條件。

案例 3：B 為黑色，B 的左子紅、右子黑

B 改紅、B 左子改黑，以 B 為支點右旋 → 必轉化為案例 4 繼續處理。

案例 4：B 為黑色，B 的左子黑、右子紅

將 P 顏色複製給 B，P 改黑、B 右子改黑，以 P 為支點左旋，將參照節點設為根 → 調整結束。

前提 2（N 為 P 的右子節點）處理流程對稱，此處略過。

C 語言完整實現

外部介面：rbt_delete

int rbt_delete(rbt_tree_t *tree, int key) {
    rbt_node_t *node = tree->root;
    if (tree->sentinel == node) return RBT_SUCCESS;
    while (tree->sentinel != node) {
        if (key == node->key) return _rb_delete(tree, node);
        else if (key < node->key) node = node->lchild;
        else node = node->rchild;
    }
    return RBT_SUCCESS;
}

內部刪除邏輯：_rb_delete

int _rb_delete(rbt_tree_t *tree, rbt_node_t *dnode) {
    rbt_node_t *parent = NULL, *next = NULL, *refer = NULL;
    // 尋找後繼節點 next
    if ((tree->sentinel == dnode->lchild) || (tree->sentinel == dnode->rchild))
        next = dnode;
    else {
        next = dnode->rchild;
        while (tree->sentinel != next->lchild) next = next->lchild;
    }
    // 設置替代節點 refer
    refer = (tree->sentinel != next->lchild) ? next->lchild : next->rchild;
    refer->parent = next->parent;
    // 更新父節點連結
    if (tree->sentinel == next->parent) tree->root = refer;
    else if (next == next->parent->lchild) next->parent->lchild = refer;
    else next->parent->rchild = refer;
    // 若刪除的是後繼節點，複製資料
    if (next != dnode) dnode->key = next->key;
    // 紅色節點直接釋放，黑色需修復
    if (rbt_is_red(next)) { free(next); return RBT_SUCCESS; }
    free(next);
    return rbt_delete_fixup(tree, refer);
}

刪除修復：rbt_delete_fixup

int rbt_delete_fixup(rbt_tree_t *tree, rbt_node_t *node) {
    rbt_node_t *parent = NULL, *brother = NULL;
    while (rbt_is_black(node) && (tree->root != node)) {
        parent = node->parent;
        if (node == parent->lchild) {
            brother = parent->rchild;
            // Case 1: 兄弟紅
            if (rbt_is_red(brother)) {
                rbt_set_red(parent); rbt_set_black(brother);
                rbt_left_rotate(tree, parent);
                brother = parent->rchild;
            }
            // Case 2: 兄弟黑且雙子皆黑
            if (rbt_is_black(brother->lchild) && rbt_is_black(brother->rchild)) {
                rbt_set_red(brother); node = parent;
            } else {
                // Case 3: 兄弟黑、左紅右黑
                if (rbt_is_black(brother->rchild)) {
                    rbt_set_black(brother->lchild); rbt_set_red(brother);
                    rbt_right_rotate(tree, brother);
                    brother = parent->rchild;
                }
                // Case 4: 兄弟黑、右紅
                rbt_copy_color(brother, parent);
                rbt_set_black(brother->rchild); rbt_set_black(parent);
                rbt_left_rotate(tree, parent);
                node = tree->root;
            }
        } else { /* 對稱處理右子節點情況 */ }
    }
    rbt_set_black(node);
    return RBT_SUCCESS;
}

驗證結果

隨機生成樹並刪除隨機節點後，結果仍滿足紅黑樹性質，經反覆驗證代碼正確。