红黑树原理与 Java 实现

红黑树是一种自平衡二叉查找树，保证了最坏情况下操作复杂度为 O(log n)。Java 的 TreeMap、HashMap（链表长度超过 8 时转红黑树）都依赖它。

从 2-3-4 树理解红黑树

红黑树本质上是把 2-3-4 树用二叉树的形式表达出来：

• 2 节点（1 key）→ 普通黑色节点
• 3 节点（2 key）→ 一个黑色节点 + 一个红色子节点
• 4 节点（3 key）→ 一个黑色节点 + 两个红色子节点

红色节点表示「我和父节点在 2-3-4 树中属于同一个节点」。

五条性质

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点（NIL）是黑色
4. 红色节点的子节点必须是黑色（不能有连续红色）
5. 从任一节点到其所有叶子节点的路径，经过的黑色节点数量相同（黑高相同）

性质 4 和 5 是核心：它们保证了树的高度不超过 2log(n+1)。

插入操作

新节点总是以红色插入，然后通过变色 + 旋转恢复平衡。

三种情况（以父节点是祖父的左孩子为例）

Case 1：叔叔是红色 → 将父和叔变黑，祖父变红，以祖父为新节点继续向上调整。

Case 2：叔叔是黑色，新节点是右孩子 → 先对父节点左旋，转换为 Case 3。

Case 3：叔叔是黑色，新节点是左孩子 → 父节点变黑，祖父变红，对祖父右旋。

Java 核心插入修复

private void fixAfterInsertion(RBNode x) {
    x.color = RED;
    while (x != root && x.parent.color == RED) {
        if (x.parent == x.parent.parent.left) {
            RBNode uncle = x.parent.parent.right;
            if (colorOf(uncle) == RED) {
                setColor(x.parent, BLACK);
                setColor(uncle, BLACK);
                setColor(x.parent.parent, RED);
                x = x.parent.parent;
            } else {
                if (x == x.parent.right) {
                    x = x.parent;
                    rotateLeft(x);
                }
                setColor(x.parent, BLACK);
                setColor(x.parent.parent, RED);
                rotateRight(x.parent.parent);
            }
        } else {
            RBNode uncle = x.parent.parent.left;
            if (colorOf(uncle) == RED) {
                setColor(x.parent, BLACK);
                setColor(uncle, BLACK);
                setColor(x.parent.parent, RED);
                x = x.parent.parent;
            } else {
                if (x == x.parent.left) {
                    x = x.parent;
                    rotateRight(x);
                }
                setColor(x.parent, BLACK);
                setColor(x.parent.parent, RED);
                rotateLeft(x.parent.parent);
            }
        }
    }
    root.color = BLACK;
}

与 AVL 树的对比

特性	红黑树	AVL 树
平衡严格度	弱平衡	强平衡
查找性能	稍差	更优
插入/删除	旋转少，更快	旋转多
适用场景	频繁增删	查找密集型

小结

理解红黑树的关键是从 2-3-4 树的视角去理解，不要死记性质。红色节点表示它和父节点在逻辑上是同一个节点，性质 4 和 5 就自然推导出来了。