深入理解红黑树（C#语言实现红黑树的插入与删除操作详解）

什么是红黑树？

红黑树是一种满足以下五条性质的二叉搜索树：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL 节点）都是黑色。
4. 如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。
5. 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点（黑高一致）。

这些规则确保了红黑树的高度始终保持在 O(log n)，从而保证了查找、插入和删除操作的时间复杂度均为 O(log n)。

C# 实现红黑树的基本结构

首先，我们定义红黑树的节点类：

public enum Color { Red, Black }public class RBNode{    public int Key;    public Color Color;    public RBNode Left;    public RBNode Right;    public RBNode Parent;    public RBNode(int key)    {        Key = key;        Color = Color.Red; // 新节点默认为红色        Left = Right = Parent = null;    }}

注意：新插入的节点默认为红色，这样可以尽量减少对黑高性质的破坏。

红黑树插入操作详解

插入操作分为两步：

1. 像普通二叉搜索树一样插入节点（作为红色节点）。
2. 通过旋转和重新着色来修复可能违反的红黑树性质。

修复过程主要处理“父节点为红色”的情况（违反性质4）。根据叔叔节点的颜色，可分为以下几种情形：

• 情况1：叔叔是红色 → 将父、叔变黑，祖父变红，然后以祖父为当前节点继续修复。
• 情况2/3：叔叔是黑色 → 需要进行左旋或右旋，并调整颜色。

以下是插入修复方法的 C# 实现：

private void InsertFixup(RBNode node){    while (node.Parent?.Color == Color.Red)    {        if (node.Parent == node.Parent.Parent.Left)        {            var uncle = node.Parent.Parent.Right;            if (uncle?.Color == Color.Red)            {                // 情况1：叔叔是红色                node.Parent.Color = Color.Black;                uncle.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                node = node.Parent.Parent;            }            else            {                if (node == node.Parent.Right)                {                    // 情况2：左-右结构，先左旋                    node = node.Parent;                    LeftRotate(node);                }                // 情况3：左-左结构，右旋                node.Parent.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                RightRotate(node.Parent.Parent);            }        }        else        {            // 对称情况（父节点是祖父的右孩子）            var uncle = node.Parent.Parent.Left;            if (uncle?.Color == Color.Red)            {                node.Parent.Color = Color.Black;                uncle.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                node = node.Parent.Parent;            }            else            {                if (node == node.Parent.Left)                {                    node = node.Parent;                    RightRotate(node);                }                node.Parent.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                LeftRotate(node.Parent.Parent);            }        }    }    root.Color = Color.Black; // 根始终为黑}

红黑树删除操作详解

删除比插入更复杂。基本步骤如下：

1. 按二叉搜索树方式删除节点。
2. 如果被删除的节点是黑色，则可能破坏黑高性质，需进行修复。

修复时，我们引入一个“双重黑色”概念（实际用一个指针表示），并通过旋转和重新着色逐步消除它。

由于篇幅限制，这里仅展示删除修复的核心逻辑框架（完整实现较复杂）：

private void DeleteFixup(RBNode node){    while (node != root && node.Color == Color.Black)    {        if (node == node.Parent.Left)        {            var sibling = node.Parent.Right;            if (sibling.Color == Color.Red)            {                sibling.Color = Color.Black;                node.Parent.Color = Color.Red;                LeftRotate(node.Parent);                sibling = node.Parent.Right;            }            if (sibling.Left?.Color == Color.Black &&                sibling.Right?.Color == Color.Black)            {                sibling.Color = Color.Red;                node = node.Parent;            }            else            {                if (sibling.Right?.Color == Color.Black)                {                    sibling.Left.Color = Color.Black;                    sibling.Color = Color.Red;                    RightRotate(sibling);                    sibling = node.Parent.Right;                }                sibling.Color = node.Parent.Color;                node.Parent.Color = Color.Black;                sibling.Right.Color = Color.Black;                LeftRotate(node.Parent);                node = root;            }        }        else        {            // 对称处理（node 是右孩子）            // ...（省略对称代码）        }    }    node.Color = Color.Black;}

总结

通过本教程，你已经掌握了 红黑树 在 C#语言 中的插入与删除核心逻辑。虽然实现细节较为复杂，但只要理解其背后的平衡思想——通过旋转和颜色调整维持五大性质——就能逐步构建出高效的自平衡树结构。

无论是面试准备还是深入学习数据结构，掌握 红黑树插入删除 都是非常有价值的技能。希望这篇 红黑树教程 能为你打下坚实基础！