紅黑樹刪除操作完整實現：修正雙黑、旋轉案例全覆蓋

刪除難點：雙黑問題

刪除黑色節點會導致該路徑黑高減 1，違反性質 5。被刪節點的替代者（後繼或子節點）若為黑，會產生「雙黑」標記，需向上傳播修正直到根或轉為紅黑平衡。

刪除總體流程

1. find() 定位目標節點 drop。
2. 按子節點數分三種情況：
   • 0 子：直接移除，若 drop 為黑 → delete_fixup(drop位置, mode=左/右)。
   • 1 子：用唯一子節點頂替，若 drop 為黑 → delete_fixup(子節點, mode)。
   • 2 子：找右子樹最小節點 suc（後繼），交換 drop 與 suc 的 value，轉為刪除 suc（至多 1 子），同樣觸發修正。
3. 修正結束後強制根節點染黑。

修正核心 delete_fixup 邏輯

參數：curnode（雙黑位置或頂替節點）、mode（0=左側雙黑, 1=右側雙黑）。

void delete_fixup(RBTree *tree, RBNode *curnode, int mode) {
    while (1) {
        if (curnode->color == RED) { // Case: 頂替節點為紅，直接染黑結束
            curnode->color = BLACK;
            if (!curnode->parent) tree->root = curnode;
            return;
        }
        RBNode *parent = curnode->parent;
        if (!parent) { tree->root = curnode; return; } // 到達根

        RBNode *uncle = (mode==0) ? parent->right : parent->left;
        if (!uncle) return; // 理論上不應發生，防禦性檢查

        if (uncle->color == RED) { // Case 1: 叔叔紅 → 父紅叔黑，旋轉父變新叔
            uncle->color = BLACK;
            parent->color = RED;
            if (mode==0) rotate_left(parent, uncle);
            else rotate_right(uncle, parent);
            // 旋轉後 uncle 成為新父，繼續循環處理
            continue;
        }

        // Case 2: 叔叔黑
        RBNode *uncle_left = uncle->left, *uncle_right = uncle->right;
        bool uncle_left_black  = !uncle_left  || uncle_left->color  == BLACK;
        bool uncle_right_black = !uncle_right || uncle_right->color == BLACK;

        if (uncle_left_black && uncle_right_black) { // 2.1 叔叔雙黑子 → 叔變紅，雙黑上傳
            uncle->color = RED;
            curnode = parent;
            mode = (parent->left == curnode) ? 0 : 1;
            continue;
        }

        // 2.2 叔叔至少一紅子 → 結束循環的關鍵旋轉
        if (mode == 0) { // 雙黑在左，關注 uncle_right
            if (uncle_right && uncle_right->color == RED) { // 2.2.1 外側紅 (LL)
                uncle->color = parent->color;
                parent->color = BLACK;
                uncle_right->color = BLACK;
                rotate_left(parent, uncle);
            } else { // 2.2.2 內側紅 (LR) → 先右旋 uncle 再左旋 parent
                uncle_left->color = BLACK;
                uncle->color = RED;
                rotate_right(uncle_left, uncle);
                // 現在 uncle_right 變紅，轉 2.2.1
                uncle->color = parent->color;
                parent->color = BLACK;
                uncle->right->color = BLACK;
                rotate_left(parent, uncle);
            }
        } else { // mode==1 對稱
            if (uncle_left && uncle_left->color == RED) { // RR
                uncle->color = parent->color;
                parent->color = BLACK;
                uncle_left->color = BLACK;
                rotate_right(uncle, parent);
            } else { // RL
                uncle_right->color = BLACK;
                uncle->color = RED;
                rotate_left(uncle, uncle_right);
                uncle->color = parent->color;
                parent->color = BLACK;
                uncle->left->color = BLACK;
                rotate_right(uncle, parent);
            }
        }
        // 旋轉後樹已平衡，curnode 更新為新子樹根（uncle），循環會在下輪因 RED 或根退出
        curnode = uncle;
    }
}

關鍵細節

• mode 傳遞「雙黑在父節點的哪一側」，決定叔叔方向與旋轉方向。
• 旋轉函數需正確維護 parent、left/right、根節點指標。
• 交換 value 而非節點指標，避免複雜的指標重掛接，簡化雙子刪除。
• 測試策略：隨機插入 1000 數，隨機刪除 500，每步驗證中序有序、黑高一致、無連續紅。

完整代碼結構

見附件 rbtree_full.c（含 insert、delete、find、mid_print、depth、black_height_check、互動式測試主迴圈）。

工程建議

1. 生產環境優先用成熟庫（Linux rbtree.h、C++ std::map/std::set、boost::intrusive::rbtree）。
2. 教學/面試手寫時，專注「插入修正三案例」+「刪除雙黑四案例」邏輯清晰表達，代碼可簡化（如不實現親指標、用遞迴）。
3. 調試利器：Graphviz 導出 .dot 視覺化樹結構，配合顏色標記瞬間定位錯誤。