如何实现C#中的红黑树算法

红黑树是一种特殊的二叉查找树，它通过给每个节点添加颜色属性（红色或黑色），并遵循特定的规则来维持树的平衡，避免二叉查找树在极端情况下退化为链表。在C#中实现红黑树，需要先明确红黑树的五个核心性质，再逐步完成节点定义、基础操作、插入删除逻辑和修复流程。

红黑树的核心性质

红黑树的五个性质是维持平衡的基础，实现时必须严格遵守：

• 每个节点要么是红色，要么是黑色
• 根节点是黑色
• 所有叶子节点（NIL节点，空节点）是黑色
• 如果一个节点是红色，那么它的两个子节点都是黑色
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

红黑树节点定义

首先定义红黑树的节点结构，包含值、颜色、父节点、左子节点、右子节点，同时定义NIL节点的静态实例用于简化空节点判断。

public enum NodeColor
{
    Red,
    Black
}

public class RedBlackTreeNode<T> where T : IComparable<T>
{
    // 节点存储的值
    public T Value { get; set; }
    // 节点颜色，默认红色
    public NodeColor Color { get; set; } = NodeColor.Red;
    // 父节点
    public RedBlackTreeNode<T> Parent { get; set; }
    // 左子节点
    public RedBlackTreeNode<T> Left { get; set; }
    // 右子节点
    public RedBlackTreeNode<T> Right { get; set; }

    // 静态NIL节点，作为所有叶子节点的统一标识
    public static readonly RedBlackTreeNode<T> Nil = new RedBlackTreeNode<T>
    {
        Color = NodeColor.Black,
        Left = null,
        Right = null,
        Parent = null
    };

    public RedBlackTreeNode(T value = default)
    {
        Value = value;
        Left = Nil;
        Right = Nil;
        Parent = Nil;
    }
}

红黑树基础操作：旋转

旋转是红黑树平衡调整的核心操作，分为左旋和右旋，用于调整节点的父子关系，维持树的结构。

左旋实现

左旋操作是将当前节点的右子节点提升为父节点，当前节点变为右子节点的左子节点，同时调整相关引用。

public class RedBlackTree<T> where T : IComparable<T>
{
    // 根节点
    public RedBlackTreeNode<T> Root { get; private set; } = RedBlackTreeNode<T>.Nil;

    // 左旋操作，node为需要旋转的节点
    private void LeftRotate(RedBlackTreeNode<T> node)
    {
        // 获取node的右子节点
        var rightChild = node.Right;
        // 将rightChild的左子节点设为node的右子节点
        node.Right = rightChild.Left;
        // 如果rightChild的左子节点不是NIL，设置其父节点为node
        if (rightChild.Left != RedBlackTreeNode<T>.Nil)
        {
            rightChild.Left.Parent = node;
        }
        // 设置rightChild的父节点为node的父节点
        rightChild.Parent = node.Parent;
        // 如果node是根节点，更新根节点为rightChild
        if (node.Parent == RedBlackTreeNode<T>.Nil)
        {
            Root = rightChild;
        }
        else if (node == node.Parent.Left)
        {
            // node是父节点的左子节点，更新父节点的左子节点为rightChild
            node.Parent.Left = rightChild;
        }
        else
        {
            // node是父节点的右子节点，更新父节点的右子节点为rightChild
            node.Parent.Right = rightChild;
        }
        // 设置rightChild的左子节点为node
        rightChild.Left = node;
        // 设置node的父节点为rightChild
        node.Parent = rightChild;
    }
}

右旋实现

右旋是左旋的镜像操作，将当前节点的左子节点提升为父节点，当前节点变为左子节点的右子节点。

// 右旋操作，node为需要旋转的节点
private void RightRotate(RedBlackTreeNode<T> node)
{
    // 获取node的左子节点
    var leftChild = node.Left;
    // 将leftChild的右子节点设为node的左子节点
    node.Left = leftChild.Right;
    // 如果leftChild的右子节点不是NIL，设置其父节点为node
    if (leftChild.Right != RedBlackTreeNode<T>.Nil)
    {
        leftChild.Right.Parent = node;
    }
    // 设置leftChild的父节点为node的父节点
    leftChild.Parent = node.Parent;
    // 如果node是根节点，更新根节点为leftChild
    if (node.Parent == RedBlackTreeNode<T>.Nil)
    {
        Root = leftChild;
    }
    else if (node == node.Parent.Right)
    {
        // node是父节点的右子节点，更新父节点的右子节点为leftChild
        node.Parent.Right = leftChild;
    }
    else
    {
        // node是父节点的左子节点，更新父节点的左子节点为leftChild
        node.Parent.Left = leftChild;
    }
    // 设置leftChild的右子节点为node
    leftChild.Right = node;
    // 设置node的父节点为leftChild
    node.Parent = leftChild;
}

红黑树插入操作与修复

红黑树的插入操作和普通二叉查找树类似，先找到插入位置，插入新节点（默认红色），然后触发插入修复流程，调整颜色和旋转以维持红黑树性质。

插入基础逻辑

// 插入新值
public void Insert(T value)
{
    var newNode = new RedBlackTreeNode<T>(value);
    var current = Root;
    RedBlackTreeNode<T> parent = RedBlackTreeNode<T>.Nil;
    // 找到插入位置
    while (current != RedBlackTreeNode<T>.Nil)
    {
        parent = current;
        if (value.CompareTo(current.Value) < 0)
        {
            current = current.Left;
        }
        else
        {
            current = current.Right;
        }
    }
    // 设置新节点的父节点
    newNode.Parent = parent;
    // 如果父节点是NIL，说明树为空，新节点作为根节点
    if (parent == RedBlackTreeNode<T>.Nil)
    {
        Root = newNode;
    }
    else if (value.CompareTo(parent.Value) < 0)
    {
        parent.Left = newNode;
    }
    else
    {
        parent.Right = newNode;
    }
    // 插入后修复红黑树性质
    InsertFixUp(newNode);
}

插入修复逻辑

插入新红色节点后，可能会违反红黑树的性质，需要根据父节点、叔叔节点的颜色情况进行修复，分为三种场景：

• 父节点是黑色：无需调整，直接结束
• 父节点是红色，叔叔节点是红色：将父节点和叔叔节点设为黑色，祖父节点设为红色，然后将祖父节点作为新的当前节点继续修复
• 父节点是红色，叔叔节点是黑色：先进行旋转调整，再调整颜色

// 插入后修复红黑树性质
private void InsertFixUp(RedBlackTreeNode<T> node)
{
    while (node.Parent.Color == NodeColor.Red)
    {
        // 父节点是祖父节点的左子节点
        if (node.Parent == node.Parent.Parent.Left)
        {
            var uncle = node.Parent.Parent.Right;
            // 场景1：叔叔节点是红色
            if (uncle.Color == NodeColor.Red)
            {
                node.Parent.Color = NodeColor.Black;
                uncle.Color = NodeColor.Black;
                node.Parent.Parent.Color = NodeColor.Red;
                node = node.Parent.Parent;
            }
            else
            {
                // 场景2：当前节点是父节点的右子节点，先左旋
                if (node == node.Parent.Right)
                {
                    node = node.Parent;
                    LeftRotate(node);
                }
                // 场景3：调整颜色并右旋
                node.Parent.Color = NodeColor.Black;
                node.Parent.Parent.Color = NodeColor.Red;
                RightRotate(node.Parent.Parent);
            }
        }
        else
        {
            // 父节点是祖父节点的右子节点，镜像逻辑
            var uncle = node.Parent.Parent.Left;
            if (uncle.Color == NodeColor.Red)
            {
                node.Parent.Color = NodeColor.Black;
                uncle.Color = NodeColor.Black;
                node.Parent.Parent.Color = NodeColor.Red;
                node = node.Parent.Parent;
            }
            else
            {
                if (node == node.Parent.Left)
                {
                    node = node.Parent;
                    RightRotate(node);
                }
                node.Parent.Color = NodeColor.Black;
                node.Parent.Parent.Color = NodeColor.Red;
                LeftRotate(node.Parent.Parent);
            }
        }
    }
    // 确保根节点是黑色
    Root.Color = NodeColor.Black;
}

红黑树删除操作与修复

红黑树的删除操作比插入更复杂，先按照二叉查找树的删除逻辑删除节点，然后根据删除节点的颜色、子节点情况触发删除修复流程。

查找最小节点

删除操作中需要找到后继节点，因此需要实现查找子树最小节点的逻辑。

// 查找以node为根的子树的最小节点
private RedBlackTreeNode<T> FindMinNode(RedBlackTreeNode<T> node)
{
    while (node.Left != RedBlackTreeNode<T>.Nil)
    {
        node = node.Left;
    }
    return node;
}

删除基础逻辑

// 删除指定值的节点
public void Delete(T value)
{
    var node = Root;
    // 查找要删除的节点
    while (node != RedBlackTreeNode<T>.Nil)
    {
        if (value.CompareTo(node.Value) == 0)
        {
            break;
        }
        else if (value.CompareTo(node.Value) < 0)
        {
            node = node.Left;
        }
        else
        {
            node = node.Right;
        }
    }
    // 没有找到要删除的节点，直接返回
    if (node == RedBlackTreeNode<T>.Nil)
    {
        return;
    }
    DeleteNode(node);
}

// 实际删除节点的逻辑
private void DeleteNode(RedBlackTreeNode<T> node)
{
    var originalColor = node.Color;
    RedBlackTreeNode<T> replaceNode;
    // 情况1：node没有左子节点
    if (node.Left == RedBlackTreeNode<T>.Nil)
    {
        replaceNode = node.Right;
        Transplant(node, node.Right);
    }
    // 情况2：node没有右子节点
    else if (node.Right == RedBlackTreeNode<T>.Nil)
    {
        replaceNode = node.Left;
        Transplant(node, node.Left);
    }
    // 情况3：node有左右两个子节点
    else
    {
        var successor = FindMinNode(node.Right);
        originalColor = successor.Color;
        replaceNode = successor.Right;
        if (successor.Parent == node)
        {
            replaceNode.Parent = successor;
        }
        else
        {
            Transplant(successor, successor.Right);
            successor.Right = node.Right;
            successor.Right.Parent = successor;
        }
        Transplant(node, successor);
        successor.Left = node.Left;
        successor.Left.Parent = successor;
        successor.Color = node.Color;
    }
    // 如果删除的原始节点是黑色，需要触发删除修复
    if (originalColor == NodeColor.Black)
    {
        DeleteFixUp(replaceNode);
    }
}

// 替换节点，将oldNode的位置替换为newNode
private void Transplant(RedBlackTreeNode<T> oldNode, RedBlackTreeNode<T> newNode)
{
    if (oldNode.Parent == RedBlackTreeNode<T>.Nil)
    {
        Root = newNode;
    }
    else if (oldNode == oldNode.Parent.Left)
    {
        oldNode.Parent.Left = newNode;
    }
    else
    {
        oldNode.Parent.Right = newNode;
    }
    newNode.Parent = oldNode.Parent;
}

删除修复逻辑

删除黑色节点后会破坏红黑树的性质，需要根据兄弟节点的颜色和子节点情况进行修复，分为四种场景：

• 兄弟节点是红色：调整颜色并旋转，将兄弟节点变为黑色
• 兄弟节点是黑色，且兄弟节点的两个子节点都是黑色：将兄弟节点设为红色，将父节点作为新的当前节点继续修复
• 兄弟节点是黑色，兄弟节点的左子节点是红色，右子节点是黑色：调整颜色并旋转，转换为下一种场景
• 兄弟节点是黑色，兄弟节点的右子节点是红色：调整颜色并旋转，完成修复

// 删除后修复红黑树性质
private void DeleteFixUp(RedBlackTreeNode<T> node)
{
    while (node != Root && node.Color == NodeColor.Black)
    {
        // node是父节点的左子节点
        if (node == node.Parent.Left)
        {
            var sibling = node.Parent.Right;
            // 场景1：兄弟节点是红色
            if (sibling.Color == NodeColor.Red)
            {
                sibling.Color = NodeColor.Black;
                node.Parent.Color = NodeColor.Red;
                LeftRotate(node.Parent);
                sibling = node.Parent.Right;
            }
            // 场景2：兄弟节点的两个子节点都是黑色
            if (sibling.Left.Color == NodeColor.Black && sibling.Right.Color == NodeColor.Black)
            {
                sibling.Color = NodeColor.Red;
                node = node.Parent;
            }
            else
            {
                // 场景3：兄弟节点的右子节点是黑色
                if (sibling.Right.Color == NodeColor.Black)
                {
                    sibling.Left.Color = NodeColor.Black;
                    sibling.Color = NodeColor.Red;
                    RightRotate(sibling);
                    sibling = node.Parent.Right;
                }
                // 场景4：兄弟节点的右子节点是红色
                sibling.Color = node.Parent.Color;
                node.Parent.Color = NodeColor.Black;
                sibling.Right.Color = NodeColor.Black;
                LeftRotate(node.Parent);
                node = Root;
            }
        }
        else
        {
            // node是父节点的右子节点，镜像逻辑
            var sibling = node.Parent.Left;
            if (sibling.Color == NodeColor.Red)
            {
                sibling.Color = NodeColor.Black;
                node.Parent.Color = NodeColor.Red;
                RightRotate(node.Parent);
                sibling = node.Parent.Left;
            }
            if (sibling.Right.Color == NodeColor.Black && sibling.Left.Color == NodeColor.Black)
            {
                sibling.Color = NodeColor.Red;
                node = node.Parent;
            }
            else
            {
                if (sibling.Left.Color == NodeColor.Black)
                {
                    sibling.Right.Color = NodeColor.Black;
                    sibling.Color = NodeColor.Red;
                    LeftRotate(sibling);
                    sibling = node.Parent.Left;
                }
                sibling.Color = node.Parent.Color;
                node.Parent.Color = NodeColor.Black;
                sibling.Left.Color = NodeColor.Black;
                RightRotate(node.Parent);
                node = Root;
            }
        }
    }
    // 将当前节点设为黑色，确保性质
    node.Color = NodeColor.Black;
}

红黑树功能验证

可以

C#红黑树数据结构算法实现修改时间：2026-06-21 22:45:38