C# 紅黑樹完整實作（下）：插入刪除旋轉核心程式碼與效能測試

紅黑樹節點定義

public class Node : INode
{
    public int Data;
    public Node Left, Right;
    public bool IsRed;
    public Node(int data) { Data = data; IsRed = true; } // 新節點預設紅
}

插入演算法核心邏輯

1. 標準 BST 插入，新節點標紅。
2. 若父節點為黑 → 完成。
3. 父節點為紅 → 違反「紅紅不可相鄰」，需修復：
   • 叔節點紅：父、叔變黑，祖變紅，向上繼續檢查。
   • 叔節點黑/不存在：依「新-父-祖」相對位置做 LL/LR/RR/RL 旋轉，旋轉後新根變黑、祖變紅，結束。
4. 根節點永遠強制為黑。

刪除演算法核心邏輯

1. 找到目標節點，若有雙子 → 用中序前驅（左子樹最右）取代值，轉為刪除前驅節點（最多一子）。
2. 實際刪除節點 tmp，子節點 newTmp 取代其位置。
3. 情況分析：
   • tmp 紅：必為葉節點，直接刪除，無違規。
   • tmp 黑、newTmp 紅：將 newTmp 染黑，修復完成。
   • 雙黑：tmp 黑、newTmp 黑/無 → 需向上回溯修復，依兄弟節點顏色與姪節點顏色分 4 大類 8 小類處理。

完整原始碼（關鍵方法）

public class RBTree : IBinaryTree
{
    private Node _head;
    private Node[] _path = new Node[64]; // 訪問路徑棧
    private int _p;                      // 棧頂索引

    // ---- 插入 ----
    public bool Add(int value)
    {
        if (_head == null) { _head = new Node(value) { IsRed = false }; return true; }

        _p = 0; Node parent = null, cur = _head;
        while (cur != null)
        {
            _path[_p++] = cur;
            if (cur.Data == value) return false;
            parent = cur;
            cur = value < parent.Data ? parent.Left : parent.Right;
        }

        cur = new Node(value); // 紅
        if (value < parent.Data) parent.Left = cur; else parent.Right = cur;
        if (!parent.IsRed) return true;

        _path[_p] = cur;
        while ((_p -= 2) >= 0)
        {
            Node gp = _path[_p], p = _path[_p + 1], ch = _path[_p + 2];
            if (!p.IsRed) break;

            Node uncle = gp.Left == p ? gp.Right : gp.Left;
            if (IsRed(uncle)) // 紅叔
            {
                p.IsRed = uncle.IsRed = false;
                if (_p > 0) gp.IsRed = true;
            }
            else // 黑叔 → 旋轉
            {
                Node newRoot = gp.Left == p
                    ? (p.Left == ch ? LL(gp) : LR(gp))
                    : (p.Right == ch ? RR(gp) : RL(gp));
                gp.IsRed = true; newRoot.IsRed = false;
                ReplaceChild(_p > 0 ? _path[_p - 1] : null, gp, newRoot);
                return true;
            }
        }
        return true;
    }

    // ---- 刪除 ----
    public bool Remove(int value)
    {
        _p = -1; Node cur = _head;
        while (cur != null)
        {
            _path[++_p] = cur;
            if (value == cur.Data) { RemoveNode(cur); return true; }
            cur = value < cur.Data ? cur.Left : cur.Right;
        }
        return false;
    }

    private void RemoveNode(Node node)
    {
        Node tmp = node;
        if (node.Left != null && node.Right != null)
        {
            tmp = node.Left; _path[++_p] = tmp;
            while (tmp.Right != null) { tmp = tmp.Right; _path[++_p] = tmp; }
            node.Data = tmp.Data; // 值前驅取代
        }

        Node newTmp = tmp.Left ?? tmp.Right;
        if (_p > 0)
        {
            Node parent = _path[_p - 1];
            if (parent.Left == tmp) parent.Left = newTmp; else parent.Right = newTmp;
            if (!tmp.IsRed && IsRed(newTmp)) { newTmp.IsRed = false; return; }
        }
        else { _head = newTmp; if (_head != null) _head.IsRed = false; return; }

        _path[_p] = newTmp;
        if (IsRed(tmp)) return; // 紅葉直接刪

        // 雙黑修復回溯
        while (_p > 0)
        {
            Node cur2 = _path[_p], par = _path[_p - 1];
            bool curIsLeft = par.Left == cur2;
            Node sib = curIsLeft ? par.Right : par.Left;

            if (IsRed(sib)) // 紅兄 → LL/RR 降為黑兄
            {
                Node newRoot = curIsLeft ? RR(par) : LL(par);
                ReplaceChild(_p > 1 ? _path[_p - 2] : null, par, newRoot);
                sib.IsRed = false; par.IsRed = true;
                _path[_p - 1] = newRoot; _path[_p] = par; _path[++_p] = cur2;
            }
            else // 黑兄
            {
                if (IsNullOrBlack(sib.Left) && IsNullOrBlack(sib.Right)) // 二黑姪
                {
                    if (par.IsRed) // 紅父
                    {
                        par.IsRed = false; sib.IsRed = true;
                        if (cur2 != null) cur2.IsRed = false; break;
                    }
                    else // 黑父
                    {
                        par.IsRed = IsRed(cur2); if (cur2 != null) cur2.IsRed = false;
                        sib.IsRed = true; _p--; // 繼續向上
                    }
                }
                else // 紅姪 → 旋轉結束
                {
                    Node newRoot;
                    if (curIsLeft)
                        newRoot = IsRed(sib.Right) ? RR(par) : RL(par);
                    else
                        newRoot = IsRed(sib.Left) ? LL(par) : LR(par);

                    if (cur2 != null) cur2.IsRed = false;
                    newRoot.IsRed = par.IsRed; par.IsRed = false;
                    ReplaceChild(_p > 1 ? _path[_p - 2] : null, par, newRoot);
                    break;
                }
            }
        }
    }

    // ---- 旋轉 ----
    private Node LL(Node r) { var l = r.Left; r.Left = l.Right; l.Right = r; return l; }
    private Node RR(Node r) { var r2 = r.Right; r.Right = r2.Left; r2.Left = r; return r2; }
    private Node LR(Node r) { var l = r.Left; var r2 = l.Right; r.Left = r2.Right; r2.Right = r; l.Right = r2.Left; r2.Left = l; return r2; }
    private Node RL(Node r) { var r2 = r.Right; var l = r2.Left; r.Right = l.Left; l.Left = r; r2.Left = l.Right; l.Right = r2; return l; }

    private void ReplaceChild(Node parent, Node oldCh, Node newCh)
    {
        if (parent != null) { if (parent.Left == oldCh) parent.Left = newCh; else parent.Right = newCh; }
        else _head = newCh;
    }
    private static bool IsRed(Node n) => n != null && n.IsRed;
    private static bool IsBlack(Node n) => n != null && !n.IsRed;
    private static bool IsNullOrBlack(Node n) => n == null || !n.IsRed;
}

效能測試對比（20 萬筆整數）

結語

紅黑樹插入/刪除均為 O(log n)，實作複雜度遠高於 AVL。實測 AVL 在隨機資料略勝一籌，紅黑樹優勢在於統計平均旋轉次數較少，適合頻繁修改場景。BCL SortedDictionary 內部即採用紅黑樹（TreeSet）。