第6章（下）：红黑树——工业界的王者

元数据卡

前置知识：AVL 树（第6章上） | 预计时间：45 分钟 | 核心难度：进阶
完成标志：能口述红黑树五条性质，能解释为什么 TreeMap 用红黑树而非 AVL

你的进度

上一节你学会了 AVL 树——用高度差限制 + 旋转保持平衡。但 AVL 太严格了，每次插入都可能触发旋转，删除时可能一路旋转到根。

现实世界需要一种更宽松的平衡约束——牺牲一点查找效率，换来更少的旋转次数。

这就是红黑树（Red-Black Tree），Java TreeMap 和 C++ std::map 的内核。

破局 · 溯源

1. 五条性质

红黑树不用高度差，用颜色来约束：

节点要么红色，要么黑色
根节点是黑色
叶节点（NIL）是黑色
红色节点的子节点必须是黑色（不能连续红色）
任意节点到每个叶节点，路径上的黑色节点数相同

这保证了最长路径不超过最短路径的两倍。规则 4 禁了连续红色，规则 5 让黑色数在各路径相等。最长路径（红黑交替）= 2 x 黑色数，最短路径（全黑）= 1 x 黑色数，所以最长 ≤ 2 x 最短。

比 AVL 宽松，但 O(log n) 仍然保证。

2. 节点定义

红黑树比 AVL 多了颜色字段和父指针——旋转时必须知道父节点是谁。

java

// 红黑树节点——等同于 Java TreeMap.Entry
class RBNode<K, V> {
    K key; V value;
    RBNode<K, V> left, right, parent;
    boolean color; // false=RED, true=BLACK
}

四个指针 + 一个颜色位。

3. 插入：为什么默认红色？

新节点是红色——红色不会违反规则 5（黑色数量不变），只可能违反规则 4（连续红色）。

这个冲突叫双红违规，修复取决于叔叔节点的颜色。

情况 1：叔叔是红色——颜色翻转。父叔变黑，祖父变红。冲突可能向上传递。

情况 2：叔叔是黑色，外侧插入（LL / RR）——旋转 + 变色。跟 AVL 的 LL/RR 思路相同。

情况 3：叔叔是黑色，内侧插入（LR / RL）——先旋转一次变外侧，再按情况 2 处理。

java

// 红黑树插入修复
// 运行: javac RBTree.java && java RBTree
public class RBTree {
    static final boolean R=false,B=true;
    class N{int v;boolean c=R;N l,r,p;N(int x){v=x;}}
    N root;

    void ins(int v){
        N n=new N(v);
        if(root==null){root=n;root.c=B;return;}
        N cur=root,par=null;
        while(cur!=null){par=cur;if(v<cur.v)cur=cur.l;else if(v>cur.v)cur=cur.r;else return;}
        n.p=par;if(v<par.v)par.l=n;else par.r=n;
        fix(n);
    }

    void fix(N n){
        while(n!=root&&n.p.c==R){
            N p=n.p,g=p.p;
            if(p==g.l){
                N u=g.r;
                if(u!=null&&u.c==R){
                    p.c=B;u.c=B;g.c=R;n=g;
                }else{
                    if(n==p.r){n=p;lRot(n);p=n.p;}
                    p.c=B;g.c=R;rRot(g);
                }
            }else{
                N u=g.l;
                if(u!=null&&u.c==R){
                    p.c=B;u.c=B;g.c=R;n=g;
                }else{
                    if(n==p.l){n=p;rRot(n);p=n.p;}
                    p.c=B;g.c=R;lRot(g);
                }
            }
        }
        root.c=B;
    }

    N rRot(N y){N x=y.l,t=x.r;x.r=y;y.l=t;if(t!=null)t.p=y;x.p=y.p;if(y.p==null)root=x;y.p=x;return x;}
    N lRot(N x){N y=x.r,t=y.l;y.l=x;x.r=t;if(t!=null)t.p=x;y.p=x.p;if(x.p==null)root=y;x.p=y;return y;}

    void pr(N n){if(n==null)return;pr(n.l);System.out.print(n.v+(n.c==B?"B":"R")+" ");pr(n.r);}
    public static void main(String[]a){
        RBTree t=new RBTree();
        for(int v:new int[]{10,20,30,15,25,5})t.ins(v);
        t.pr(t.root);
    }
}
// 输出: 5R 10B 15R 20B 25R 30R（实际颜色因插入顺序而异）

核心模式：

外侧（LL/RR） → 一次旋转 + 变色。内侧（LR/RL） → 两次旋转 + 变色。叔叔红色 → 只变色，不旋转（向上传递）。

4. 为什么 TreeMap 选红黑树而不是 AVL ？

维度	AVL	红黑树
查找速度	更快（严格 log n）	稍慢（最多 2log n）
插入/删除旋转	可能 O(log n) 次	最多 2~3 次
实现复杂度	相对简单	更复杂
空间开销	height（整数）	color（1 位）

TreeMap 是通用组件——插入、删除、查找都做。对通用组件来说，写操作效率更关键。红黑树插入最多 2 次旋转，删除最多 3 次，而 AVL 可能有 O(log n) 次。

如果是读远多于写的场景（比如建一次索引疯狂查询），AVL 更好——树更矮，查找更快。

5. 应用场景

应用：Java TreeMap/TreeSet、C++ std::map、Linux CFS 调度器都选红黑树（写操作多）。只读索引选 AVL/B+ 树（读远多于写）。

常见陷阱

忘记把根设为黑色。 root.c = B 这一行不是多余的——情况 1 的颜色翻转可能把根变红。

父指针链接出错。 红黑树旋转需要更新父指针，这是最常见的 bug 来源。AVL 沿递归回溯修复不需要父指针，但红黑树不行。

通关挑战

口述五条性质，推导"最长路径 ≤ 2 x 最短路径"
手画插入 [10, 20, 30] 到红黑树的过程，标每一步的颜色
解释"新节点为什么是红色？"（规则 5 的原因）

验收标准

[ ] 能口述五条性质，推导最长 ≤ 2 x 最短
[ ] 能说出 TreeMap 选红黑树的原因（写操作旋转少）
[ ] 能说出红黑树和 AVL 的核心取舍

常见卡点

双红修复记不住？ 叔叔是决策中心：叔叔红色 → 颜色翻转；叔叔黑色 → 旋转 + 变色（外侧一次，内侧两次）。

红黑树的旋转跟 AVL 一样吗？ 完全一样。区别只在于判断条件——AVL 看高度，红黑树看颜色。

旅人笔记

红黑树是 AVL 的工业改良版——用更宽松的平衡（2x 路径差）换来更少的旋转次数。它是 Java TreeMap 和 C++ std::map 的内核。记住：新节点是红色，叔叔帮你决定怎么修。

下一步

树的故事告一段落。下一章从"树"转向一种新结构——堆。BST 关注"左小右大"，堆关注"父节点 >= 子节点"。BST 用来查找，堆用来维护最值。PriorityQueue、堆排序、Top-K 都在那里。

→ 堆与优先队列

第6章（下）：红黑树——工业界的王者 ​

1. 五条性质 ​

2. 节点定义 ​

3. 插入：为什么默认红色？ ​

4. 为什么 TreeMap 选红黑树而不是 AVL ？ ​