红黑树实现

介绍

红黑树(RBT, Red Black Tree)是一种自平衡的二叉搜索树，有如下定义：

• 根叶黑：根和叶子节点是黑色的（红黑树里的叶子节点其实是空节点Nil）
• 不红红：红色节点的两个子节点都必须是黑色。（即不能有两个连续的红色节点）
• 黑同路：从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点

在这种定义下确保从根到叶子的最长路径不会超过最短路径的两倍，从而保证了高效的查找、插入和删除操作。相较于AVL树的严格平衡，红黑树只求得一种弱平衡，因此它的插入/删除性能是优于AVL树的，但是查询性能则略逊于AVL树。C++里的set、map底层就是红黑树实现的。

插入

插入一般是破坏“不红红”规则，这种情况下，自己是红色的，父亲是红色的，爷爷是黑色的，只有叔叔是一个变量

• 当叔叔是红色时，此时当前子树已经无法通过自己内部来“消化”，必须依靠更上一层的节点来处理，因此爷爷的黑色下沉到父亲和叔叔，爷爷变成红色，随后再由更上一层来处理
• 当叔叔是黑色时，此时当前子树是有能力来处理的。二叉树的旋转，说白了就是降低树高，此时子根的两个孩子中的红节点形成的链条，发现已经出现了“偏斜”，所以进行二叉树的旋转，将红色节点相对均衡分布到新的子根的两侧，从而解决不红红的问题

删除

• 删除节点的主要思路与一般的二叉搜索树相似，值得注意点是，当待删除的节点拥有左右孩子时，需要通过覆盖的形式，转换为删除它的后继节点，这样最终要删除的节点必定是最多只有一个孩子的节点。
• 分析只有一个孩子节点的情况时，发现只会存在1种情况：待删除的节点是黑色的，且它的子树（左或右）必然只有一个红色节点。如同下面图示所示，你会发现，其他情况都会导致与定义冲突。因此删除操作十分简单，删除后将它的红孩子替代过来，然后将它置黑以维持黑路同。
• 分析不包含任何孩子的节点情况时，如果是红色节点，直接删除即可。但要是黑色节点，则会变得十分复杂，以待删除节点的父亲节点为根的子树范围内出现了黑路同问题。但好在，根据红黑树的性质，待删除节点必然有一个兄弟（删除前黑路同），我们可以以这个兄弟为变量进行处理。
  • 当兄弟是黑色的时候：
    我们本能会想，将兄弟变红，兄弟这条子树的黑节点就会减去1，然后再把难题推给父亲，但是兄弟有红色孩子怎么办呢，所以要进行区分：
    • 当兄弟有红色孩子的时候：
      将兄弟变红的想法不能直接用了，但是侄子既然有红色，那就代表有回旋的余地。我们可以通过旋转将这个侄子推到最上面成为新子树的根，然后旧子树的根就可以放心置黑以平衡被删除的黑色节点，这样在该子树范围内就可以解决删除带来的问题！但是别忘了，其他未受影响的子树的路径颜色必须保持一致，因此需要进行一系列的颜色继承操作。比如LL和RR，需要先由侄子继承兄弟的颜色，然后兄弟继承父亲的颜色，再将父亲置黑，最后旋转，兄弟成为新子树的根；LR和RL，则是需要侄子直接继承父亲的颜色，再将父亲置黑，最后旋转，侄子成为新子树的根。
    • 当兄弟没有红色孩子的时候：
      我们可以将兄弟直接变成红色了！随后难题交给父亲节点。值得注意的是，如果父亲是红色节点，那么超级简单，直接变成黑色，弥补少的一个节点。如果父亲节点是根节点，则不用处理了，相当于整棵树的所有路径经过的黑色节点都-1，这依旧满足黑路同。
  • 当兄弟是红色的时候：
    这个红色非常碍事，我们想把他转化为黑色的兄弟，然后套用上面的处理方式，但是不能直接置黑，这样使得局面更乱。通过草稿纸上疯狂绘图，发现，简单的改色根本无能为力，但是如果我们将待删除节点的父亲向着待删除节点的方向进行旋转并且将旋转点和支点这两个节点的颜色取反，就能够保证其他未受影响的子树的路径信息不会发生改变。最终形成的新树中，“不平衡”的问题被收缩到了一个更小的范围，此时惊喜的发现，待删除节点的新兄弟，是黑色的。此时，我们可以套用上面处理黑色兄弟时的方法来进行操作了！

图示

public enum Color
{
    Red,
    Black,
}

public class TNode
{
    public readonly static TNode Nil = new();

    public int Key;
    public Color Color;
    public TNode Parent;
    public TNode Left;
    public TNode Right;

    public TNode Sibling => (Parent.Left == this) ? Parent.Right : Parent.Left;
    public TNode Grandpa => Parent.Parent;
    public TNode Uncle => (Grandpa.Left == Parent) ? Grandpa.Right : Grandpa.Left;

    // Nil节点（黑）
    private TNode()
    { 
        Color = Color.Black;
        Parent = Left = Right = this;
    }

    // 其他节点
    public TNode(int key)
    {
        Key = key;
        Parent = Left = Right = Nil;
    }

    public override string ToString()
    {
        if (Parent == this)
            return "NIL";
        string show = $"Color: {Color}, ";
        show += "Left: " + (Left == Nil ? "NIL" : Left.Key.ToString()) + ", ";
        show += $"Me: {Key}, ";
        show += "Right: " + (Right == Nil ? "Nil" : Right.Key.ToString()) + ", ";
        show += "Parent: " + (Parent == Nil ? "Nil" : Parent.Key.ToString());
        return show;
    }
}

public class RBTree
{
    private TNode Root = TNode.Nil;

    public RBTree() { }

    public RBTree(int[] keys)
    {
        foreach (var key in keys)
            Insert(key);
    }

    public void Insert(int key)
    {
        var explorer = Root;
        var behind = explorer;
        while (explorer != TNode.Nil)
        {
            behind = explorer;
            if (key > explorer.Key)
                explorer = explorer.Right;
            else if (key < explorer.Key)
                explorer = explorer.Left;
            else
                return;
        }
        var newNode = new TNode(key) { Parent = behind, Color = Color.Red };
        if (behind != TNode.Nil)
        {
            if (key > behind.Key)
                behind.Right = newNode;
            else
                behind.Left = newNode;
        }
        else
        {
            // 插入根
            Root = newNode;
        }
        // 尝试循环调整
        var checkNode = newNode;
        do { checkNode = FixupAfterInsert(checkNode); }
        while (checkNode != TNode.Nil);
    }

    private TNode FixupAfterInsert(TNode node)
    {
        // 根叶黑
        if (node == Root)
        {
            node.Color = Color.Black;
            return TNode.Nil;
        }
        // !不红红
        if (node.Parent.Color == Color.Black)
            return TNode.Nil;

        // 处理叔叔是红色节点的情况 -> 黑下沉，红冒泡，抛出问题，交由上层去处理
        // 叔、父、爷变色，进一步处理爷爷
        if (node.Uncle.Color == Color.Red)
        {
            node.Uncle.Color = Color.Black;
            node.Parent.Color = Color.Black;
            node.Grandpa.Color = Color.Red;
            return node.Grandpa;
        }
        // 处理叔叔是黑色节点的情况 -> 叔叔黑色，所以可以自由进行旋转，由偏链转为对称链，即可在子树范围内解决问题
        // 四种旋转，旧、新根变色
        else
        {
            node.Grandpa.Color = Color.Red;
            if (node.Grandpa.Left == node.Parent)
            {
                if (node.Parent.Left == node)
                {
                    node.Parent.Color = Color.Black;
                    RightRotation(node.Grandpa);
                }
                else
                {
                    node.Color = Color.Black;
                    LR(node.Grandpa);
                }
            }
            else
            {
                if (node.Parent.Left == node)
                {
                    node.Color = Color.Black;
                    RL(node.Grandpa);
                }
                else
                {
                    node.Parent.Color = Color.Black;
                    LeftRotation(node.Grandpa);
                }
            }
            return TNode.Nil;
        }
    }

    public void Remove(int key)
    {
        var explorer = Root;
        while (explorer != TNode.Nil)
        {
            if (key > explorer.Key)
                explorer = explorer.Right;
            else if (key < explorer.Key)
                explorer = explorer.Left;
            else
            {
                // 没有孩子
                if (explorer.Left == TNode.Nil && explorer.Right == TNode.Nil)
                {
                    // 删除单个黑节点：可能需要多次循环处理
                    if (explorer.Color == Color.Black)
                    {
                        var dealNode = explorer;
                        do { dealNode = FixupBeforeRemove(dealNode); }
                        while (dealNode != TNode.Nil);
                    }
                    // 删除普通节点
                    if (explorer != Root)
                    {
                        if (explorer.Parent.Left == explorer)
                            explorer.Parent.Left = TNode.Nil;
                        else
                            explorer.Parent.Right = TNode.Nil;
                    }
                    // 删除根节点 -> 变成空节点
                    else
                        Root = TNode.Nil;
                    return;
                }
                // 只有一个孩子 -> 替代后变黑
                else if (explorer.Left == TNode.Nil || explorer.Right == TNode.Nil)
                {
                    var successor = explorer.Left == TNode.Nil ? explorer.Right : explorer.Left;
                    successor.Parent = explorer.Parent;
                    if (explorer.Parent != TNode.Nil)
                    {
                        if (explorer.Parent.Left == explorer)
                            explorer.Parent.Left = successor;
                        else
                            explorer.Parent.Right = successor;
                    }
                    successor.Color = Color.Black;
                    // 删除根节点 -> 新根继位
                    if (explorer == Root)
                        Root = successor;
                    return;
                }
                // 两个孩子，后继节点代替，随后去移除后继节点
                else
                {
                    var successor = explorer.Right;
                    while (successor.Left != TNode.Nil)
                        successor = successor.Left;
                    explorer.Key = successor.Key;
                    key = successor.Key;
                    explorer = explorer.Right;
                }
            }
        }
    }

    private TNode FixupBeforeRemove(TNode node)
    {
        if (node == Root)
            return TNode.Nil;

        // 兄弟是红色 -> 转换成兄弟是黑色
        if (node.Sibling.Color == Color.Red)
        {
            // 兄弟红色，需要转换（保留待删除的节点）
            node.Sibling.Color = node.Parent.Color;
            node.Parent.Color = Color.Red;
            if (node.Parent.Left == node)
                LeftRotation(node.Parent);
            else
                RightRotation(node.Parent);
            return node;
        }
        // 兄弟是黑色
        else
        {
            // 有红侄子：处理后结束
            if (node.Sibling.Left.Color == Color.Red || node.Sibling.Right.Color == Color.Red)
            {
                if (node.Parent.Left == node.Sibling)
                {
                    if (node.Sibling.Left.Color == Color.Red)
                    {
                        node.Sibling.Left.Color = node.Sibling.Color;
                        node.Sibling.Color = node.Parent.Color;
                        node.Parent.Color = Color.Black;
                        RightRotation(node.Parent);
                    }
                    else
                    {
                        node.Sibling.Right.Color = node.Parent.Color;
                        node.Parent.Color = Color.Black;
                        LR(node.Parent);
                    }
                }
                else
                {
                    if (node.Sibling.Left.Color == Color.Red)
                    {
                        node.Sibling.Left.Color = node.Parent.Color;
                        node.Parent.Color = Color.Black;
                        RL(node.Parent);
                    }
                    else
                    {
                        node.Sibling.Right.Color = node.Sibling.Color;
                        node.Sibling.Color = node.Parent.Color;
                        node.Parent.Color = Color.Black;
                        LeftRotation(node.Parent);
                    }
                }
                return TNode.Nil;
            }
            // 全是黑侄子
            else
            {
                var parent = node.Parent;
                node.Sibling.Color = Color.Red;

                // 如果父亲是根节点，直接返回
                if (parent == Root)
                    return TNode.Nil;

                // 如果父节点是红色，变黑即可
                if (parent.Color == Color.Red)
                {
                    parent.Color = Color.Black;
                    return TNode.Nil;
                }
                return parent;
            }
        }
    }

    private void LeftRotation(TNode node)
    {
        var outParent = node.Parent;
        var rightNode = node.Right;
        var rightLeftNode = rightNode.Left;

        rightNode.Left = node;
        node.Parent = rightNode;

        node.Right = rightLeftNode;
        if (rightLeftNode != TNode.Nil)
            rightLeftNode.Parent = node;

        rightNode.Parent = outParent;
        if (node != Root)
        {
            if (outParent.Left == node)
                outParent.Left = rightNode;
            else
                outParent.Right = rightNode;
        }
        else
        {
            Root = rightNode;
        }
    }

    private void RightRotation(TNode node)
    {
        var outParent = node.Parent;
        var leftNode = node.Left;
        var leftRightNode = leftNode.Right;

        leftNode.Right = node;
        node.Parent = leftNode;

        node.Left = leftRightNode;
        if (leftRightNode != TNode.Nil)
            leftRightNode.Parent = node;

        leftNode.Parent = outParent;
        if (node != Root)
        {
            if (outParent.Left == node)
                outParent.Left = leftNode;
            else
                outParent.Right = leftNode;
        }
        else
        {
            Root = leftNode;
        }
    }

    private void LR(TNode node)
    {
        var leftNode = node.Left;
        LeftRotation(leftNode);
        RightRotation(node);
    }

    private void RL(TNode node)
    {
        var rightNode = node.Right;
        RightRotation(rightNode);
        LeftRotation(node);
    }

    public void ShowLog()
    {
        StringBuilder sb = new("层序遍历：\n");
        DoShowLog(sb);
        Console.WriteLine(sb);
    }

    private int GetHeight(TNode node)
    {
        if (node == TNode.Nil)
            return 0;
        var leftHeight = GetHeight(node.Left);
        var rightHeight = GetHeight(node.Right);
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    private void DoShowLog(StringBuilder sb)
    {
        Queue<TNode?> queue = new();
        queue.Enqueue(Root);
        int curLayer = 0;
        int totalLayer = GetHeight(Root);
        while (queue.Count > 0)
        {
            int count = queue.Count;
            string layerOutput = "";
            ++curLayer;
            bool isFirstSiblingInCurrentLayer = true;
            for (int i = 0; i < count; ++i)
            {
                var indent = (int)(Math.Pow(2, (totalLayer - curLayer)));
                if (curLayer > 1 && !isFirstSiblingInCurrentLayer)
                    indent <<= 1;

                var curNode = queue.Dequeue();
                if (curNode != TNode.Nil && curNode != null)
                {
                    var mark = (curNode.Color == Color.Red) ? 'R' : 'B';
                    layerOutput += Indent(indent - 1) + mark + curNode.Key.ToString().PadLeft(3, ' ');
                    queue.Enqueue(curNode.Left);
                    queue.Enqueue(curNode.Right);
                }
                else if (curLayer <= totalLayer)
                {
                    layerOutput += Indent(indent - 1) + "NULL";
                    if (curLayer < totalLayer)
                    {
                        queue.Enqueue(null);
                        queue.Enqueue(null);
                    }
                }
                isFirstSiblingInCurrentLayer = false;
            }
            sb.AppendLine(layerOutput);
            sb.AppendLine();
        }
    }

    private static string Indent(int n)
    {
        return string.Concat(Enumerable.Repeat("    ", n));
    }
}

Why红黑树？

“红黑树这几条武断的规则凭什么有效果”是我学习红黑树时常常嘀咕的问题，以为红黑树纯粹是工程经验的产物。但请教DeepSeek后发现事情远没有这么简单。以下是DeepSeek的解释：

红黑树并不是某个人凭空“琢磨”出来的完美规则，而是对另一种更早、更复杂的数据结构——“2-3-4树”（或称B树的一种）——的一种优雅的“翻译”或“模拟”。
在红黑树之前，人们已经有了2-3-4树。这种树不是二叉树，它的节点可以有1、2或3个键值和2、3或4个子节点（即2、3、4阶B树）。正是这种“多键值节点”的特性，保证了2-3-4树是绝对平衡的——从根节点到所有叶子节点的路径长度完全相同。
这时，计算机科学家们（特别是Rudolf Bayer，他首先提出了等价结构，后来Leo Guibas和Robert Sedgewick将其标准化并引入了“颜色”的概念）思考：能否用一种大家更熟悉的、标准的二叉树来模拟2-3-4树的行为，同时保持其平衡特性呢？
答案是：可以！红黑树就是这场“翻译”的结果。
让我们看看这场“翻译”是如何进行的：
2-3-4树中的2-节点：就是一个普通的二叉树节点。
红黑树翻译：一个黑色的节点。
2-3-4树中的3-节点：包含两个键值（A, B）和三个子节点。
红黑树翻译：有两种等价的表示方法。可以看作是 A(黑) -> B(红)，或者 B(黑) -> A(红)。无论哪种，这个结构都由一黑一红两个节点组成，红色节点表示它和父节点在2-3-4树中原本是“平级”的。
2-3-4树中的4-节点：包含三个键值（A, B, C）和四个子节点。
红黑树翻译：一个黑色节点（B）带着两个红色子节点（A和C）。这表示A、B、C在2-3-4树中属于同一个节点。

现在，我们再回头看红黑树的五条规则，你会发现它们不再是凭空捏造，而是对2-3-4树特性的直接描述：
节点是红色或黑色。
为什么？ 因为我们需要用颜色来标记一个节点在2-3-4树中是与父节点“合并”在一起的（红色），还是一个独立的节点（黑色）。
根节点是黑色。
为什么？ 2-3-4树的根节点可以是任意类型（2-,3-,4-节点），但它的顶部没有父节点，所以它翻译过来自然就是黑色的。这也避免了在旋转等操作时根节点可能变为红色的情况。
所有叶子节点（NIL节点）都是黑色。
为什么？ 这是为了定义清晰。这些NIL节点代表不存在的子节点，将它们统一视为黑色，可以简化规则的定义和代码实现。
红色节点的两个子节点都是黑色。（即：不能有两个连续的红色节点）
这是核心规则！为什么？ 因为在2-3-4树的翻译中，一个红色节点代表它和它的黑色父节点原本在同一个多键值节点里。这个多键值节点内部不可能再嵌套另一个多键值节点。所以红色节点下面不能再接红色节点，否则就违反了2-3-4树的结构。
从任一节点到其每个叶子（NIL）的所有路径都包含相同数目的黑色节点。
这是平衡性的保证！为什么？ 这正是2-3-4树“绝对平衡”特性的体现。在2-3-4树中，从根到所有叶子的路径长度相同。在翻译成红黑树时，路径上的黑色节点数量就代表了在2-3-4树中经过的“真实节点”的数量。无论你怎么走，经过的黑色节点数（即2-3-4节点数）一定是相等的。

当您理解了这层关系，红黑树复杂的插入和删除修复操作（变色、旋转）就不再是魔法，它们只不过是在模拟2-3-4树的节点分裂与合并！
插入：
在红黑树中，我们总是先插入为红色节点。这相当于尝试向一个2-3-4树的节点中添加一个新元素。
如果导致两个连续的红色节点（规则4被打破），这等价于在2-3-4树中形成了一个非法的 5-节点（有4个元素）。
此时的修复操作（变色、旋转），正是在模拟2-3-4树中对一个过满节点（5-节点）的分裂过程！您可以将修复过程中的每一次变色和旋转，都映射回一个节点分裂的动作。
删除：
删除操作更为复杂，但其修复过程同样是在模拟2-3-4树中的节点合并或借用兄弟节点元素的过程，以保持树的平衡。

结论：设计者的思维路径
现在，我们可以回答您最初的问题了：设计者是如何琢磨出这些规则的？
起点：他们拥有一个理论上完美平衡但实现复杂的数据结构——2-3-4树（4阶B树）。
目标：能否用一种更简单、更通用的二叉树来实现它，从而获得其平衡性的好处，同时规避实现的复杂性？
洞察（关键一步）：他们发现，可以用链接的颜色作为标记，来区分一个节点是独立的（黑链接），还是与父节点属于2-3-4树中的同一个逻辑节点（红链接）。
编码：他们将2-3-4树的特性“翻译”成了一组适用于这种带颜色标记的二叉树的规则。这些规则（红黑树的五条定义）确保了二叉树始终是2-3-4树的一个合法投影。
优化：基于这套规则，他们设计出了一套维护算法（插入、删除后的修复），这些算法本质上是在二进制世界里高效地模拟2-3-4树的节点分裂与合并。
所以，红黑树并非凭空想象的产物，而是一个工程上的杰作。它通过一个巧妙的“表示层”，将一种复杂的、理想化的模型，适配到了一个简单、高效的通用结构上。它牺牲了AVL树那种极致的严格平衡，换来了在频繁修改场景下更少的调整开销，这正是因为它底层模拟的2-3-4树本身就比AVL树“宽松”一些。

参考文献

• Bilibili蓝不过海啊的红黑树视频
• Bilibili哈哈哈哈陈的红黑树视频
• DeepSeek