深入理解红黑树（C#语言实现与平衡调整规则详解）

为什么需要平衡调整？

当我们向红黑树中插入或删除节点时，可能会破坏上述五条性质。为了恢复这些性质，我们需要执行一系列的旋转（rotation）和重新着色（recoloring）操作，这就是所谓的“平衡调整”。

在 C# 中实现红黑树时，我们通常会定义一个节点类：

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

插入后的平衡调整规则（C# 实现核心）

插入新节点后，可能违反红黑树的性质（尤其是第 4 条：红节点不能有红孩子）。我们通过以下三种情况来修复：

情况 1：叔叔节点是红色

此时我们将父节点和叔叔节点设为黑色，祖父节点设为红色，然后以祖父节点为当前节点继续向上检查。

情况 2：叔叔节点是黑色，且当前节点是右孩子（而父节点是左孩子）

这时需要对父节点做一次左旋，转化为情况 3。

情况 3：叔叔节点是黑色，且当前节点是左孩子（父节点也是左孩子）

将父节点设为黑色，祖父节点设为红色，然后对祖父节点做一次右旋。

注意：以上是“父节点为左孩子”的情形；若父节点是右孩子，则左右对称处理（右旋变左旋，左孩子变右孩子）。

下面是一个简化的 C# 平衡调整方法（InsertFixup）：

private void InsertFixup(RBNode node){    while (node.Parent?.Color == Color.Red)    {        if (node.Parent == node.Parent.Parent.Left)        {            RBNode uncle = node.Parent.Parent.Right;            // 情况1：叔叔是红色            if (uncle != null && uncle.Color == Color.Red)            {                node.Parent.Color = Color.Black;                uncle.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                node = node.Parent.Parent;            }            else            {                // 情况2：node 是右孩子                if (node == node.Parent.Right)                {                    node = node.Parent;                    LeftRotate(node);                }                // 情况3                node.Parent.Color = Color.Black;                node.Parent.Parent.Color = Color.Red;                RightRotate(node.Parent.Parent);            }        }        else        {            // 对称处理（父节点是右孩子）            RBNode uncle = node.Parent.Parent.Left;            if (uncle != null && 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; // 确保根始终为黑色}

旋转操作详解

旋转是红黑树调整的核心。以右旋为例：

private void RightRotate(RBNode x){    RBNode y = x.Left;    x.Left = y.Right;    if (y.Right != null)        y.Right.Parent = x;    y.Parent = x.Parent;    if (x.Parent == null)        root = y;    else if (x == x.Parent.Left)        x.Parent.Left = y;    else        x.Parent.Right = y;    y.Right = x;    x.Parent = y;}

左旋（LeftRotate）逻辑类似，只需将 Left/Right 互换即可。

总结

通过本教程，你已经掌握了 红黑树的基本性质、插入后的平衡调整规则，以及如何用 C#语言实现关键的修复逻辑。虽然红黑树的调整逻辑初看复杂，但只要理解三种情况及其转换关系，就能轻松驾驭。

无论是面试准备还是深入学习数据结构教程，红黑树都是不可绕过的重要内容。建议你动手编写完整代码并调试，加深理解。

希望这篇关于 C#红黑树实现 的教程对你有所帮助！