15.TreeMap与红黑树原理

目录介绍

• 1. 案例引入
  • 1.1 排行榜的烦恼
  • 1.2 一次延迟翻车
  • 1.3 我们要回答什么
• 2. 有序映射全景
  • 2.1 三种实现对比
  • 2.2 平衡树家族谱
  • 2.3 选型决策路径
• 3. 红黑树五大性质
  • 3.1 性质条文逐条
  • 3.2 黑高与最长路径
  • 3.3 性质保证的本质
• 4. 节点结构剖析
  • 4.1 Entry 字段布局
  • 4.2 颜色位的存放
  • 4.3 父指针的代价
• 5. 旋转操作根基
  • 5.1 左旋几何直觉
  • 5.2 右旋几何直觉
  • 5.3 旋转的不变式
• 6. 插入调整规则
  • 6.1 五种局面分类
  • 6.2 叔叔红色情形
  • 6.3 叔叔黑色情形
  • 6.4 完整插入示例
• 7. 删除调整规则
  • 7.1 删除的本质
  • 7.2 双黑节点危机
  • 7.3 四种修复局面
• 8. 跳表对比分析
  • 8.1 跳表结构原理
  • 8.2 复杂度对比
  • 8.3 并发友好性
• 9. ConcurrentSkipListMap
  • 9.1 为什么不用红黑树
  • 9.2 跳表的无锁化
  • 9.3 三大有序 Map 对比
• 10. 综合案例串讲
  • 10.1 排行榜真相揭晓
  • 10.2 一次 put 的红黑路径
  • 10.3 设计哲学回扣
  • 10.4 有序容器速查表

1. 案例引入

1.1 排行榜的烦恼

某电商团队做"实时积分排行榜"——每个用户有积分 score，要支持 4 个查询：

查询 1：top(K)              取前 K 名
查询 2：rank(userId)        查某人是第几名
查询 3：around(userId, n)   查某人前后 n 位
查询 4：put(userId, score)  更新某人积分

第一版用 HashMap<Long, Integer> 存（userId → score），结果发现：

public List<Long> top(int k) {
    return userScores.entrySet().stream()
        .sorted(Map.Entry.<Long, Integer>comparingByValue().reversed())
        .limit(k)
        .map(Map.Entry::getKey)
        .toList();
}

每次 top(K) 都要把 100 万用户全排序一遍 → O(n log n) → 单次 800ms。leader 看到监控直接退回了。

第二版换成 TreeMap<Integer, Set<Long>>（score → userIds，按 score 倒序）：

private final TreeMap<Integer, Set<Long>> rankMap = 
    new TreeMap<>(Comparator.reverseOrder());

top(K) 性能从 800ms → 0.5ms——用 TreeMap 内置的有序遍历替代了全排序。性能起飞。

1.2 一次延迟翻车

但好景不长，半年后流量翻倍，监控告警：rank() 的 P99 从 2ms 飙到 50ms。jstack 没死锁，CPU 也不高，但 TreeMap 操作明显变慢。

排查时同事甩出三个灵魂质问：

追问 ①：TreeMap 的 get/put/rank 是 O(log n)，n 翻倍只该多 1 层比较，
         为什么延迟 P99 翻 25 倍？
追问 ②：TreeMap 底层是红黑树。它的"5 大性质"到底保证了什么？
         为什么是这 5 条而不是 4 条或 6 条？
追问 ③：JDK 自带 ConcurrentSkipListMap，为啥不直接做"线程安全 TreeMap"？
         红黑树有什么"不能并发"的硬伤？

更扎心的是——插入一个新元素，最多触发多少次旋转？最多重染色多少次？没人答得上。这一切，就是本篇要回答的核心。

1.3 我们要回答什么

第 21 篇要把"有序映射"这件事讲透——从红黑树五大性质的数学本质，到 ConcurrentSkipListMap 用跳表而非红黑树的工程考量。

带着这个目标，要回答 7 个核心问题：

① 红黑树的"5 大性质"分别是什么？为什么这 5 条能保证 O(log n)？  → 第3章
② 黑高 (black height) 是什么？最长路径为什么不超过最短路径 2 倍？ → 第3章
③ 插入调整最多旋转几次？删除调整呢？复杂度的常数项是多少？     → 第6-7章
④ 旋转操作怎么保证 BST 性质不变？左旋右旋是怎么"对偶"的？      → 第5章
⑤ 跳表与红黑树相比，复杂度和空间各有什么取舍？               → 第8章
⑥ ConcurrentSkipListMap 为什么不基于红黑树做并发版本？        → 第9章
⑦ TreeMap、ConcurrentSkipListMap、ConcurrentHashMap 怎么选？  → 第9-10章

本篇路线：

有序映射全景 (第2章) ─── 红黑树 / AVL / 跳表三足鼎立
    ↓
红黑树五大性质 (第3章)     ←—— 数学根基
节点结构剖析 (第4章)       ←—— 颜色位放在哪
旋转操作根基 (第5章)       ←—— 平衡的物理工具
    ↓
插入调整规则 (第6章)       ←—— 5 种局面 + 完整示例
删除调整规则 (第7章)       ←—— 双黑危机 4 种修复
    ↓
跳表对比分析 (第8章)
ConcurrentSkipListMap (第9章)  ←—— 为什么放弃红黑树
    ↓
综合案例串讲 (第10章)

2. 有序映射全景

2.1 三种实现对比

JDK 中"有序 Map"有三种实现，对应三种数据结构哲学：

┌─────────────────────────────────────────────────────────┐
│ TreeMap                                                  │
│   底层：红黑树 (Red-Black Tree)                           │
│   特点：自平衡 BST，旋转保证 O(log n)                      │
│   并发：非线程安全                                         │
│   场景：单线程有序 Map 默认选择                            │
└─────────────────────────────────────────────────────────┘
                          ↓
┌─────────────────────────────────────────────────────────┐
│ ConcurrentSkipListMap                                    │
│   底层：跳表 (Skip List)                                 │
│   特点：多层链表，CAS 友好，无锁可并发                      │
│   并发：线程安全                                          │
│   场景：高并发有序 Map                                     │
└─────────────────────────────────────────────────────────┘
                          ↓
┌─────────────────────────────────────────────────────────┐
│ Collections.synchronizedSortedMap(new TreeMap<>())       │
│   底层：TreeMap + 全表锁                                  │
│   特点：粗粒度锁，简单但慢                                  │
│   并发：线程安全（差）                                     │
│   场景：低并发兼容旧代码                                   │
└─────────────────────────────────────────────────────────┘

疑惑：既然 TreeMap 已经做到 O(log n)，为什么并发场景不直接给它加锁？

论证：红黑树的旋转操作要修改多个父子指针，而且修改路径从插入点回溯到根节点。在并发场景：

• 写线程 A 正在做"叔叔红色"的重染色（自下而上回溯）
• 写线程 B 同时插入到另一棵子树，也要回溯到根
• 两个线程在根节点附近必然冲突

如果给红黑树加锁，要么"全树锁"（退回 Hashtable 时代），要么"自下而上的细粒度锁"（极易死锁）。两条路都不通。

结论：红黑树本身的"指针密集修改"是它无法高效并发的根本原因。这就是为什么 Doug Lea 在 2007 年专门写了 ConcurrentSkipListMap 而不是"ConcurrentTreeMap"——选错数据结构，再多努力也救不回来。

2.2 平衡树家族谱

平衡树家族成员众多，按"约束严格度"排列：

约束最松 ─────────────────────────────────────→ 约束最严
   │                                              │
   │                                              │
跳表 ── 红黑树 ── Treap ── B 树 ── B+树 ── AVL 树
                                                  │
                                              旋转最多
                                              查询最快
                                              插入最慢

关键观察：约束越严的树，查询越快但写入越慢：

树型	平衡约束	查询	插入旋转上限
AVL	任意节点左右子树高度差 ≤ 1	最快	O(log n) 次
红黑树	黑高相等、红节点不连续	较快	≤ 3 次
B 树	节点容量上下界	中等	O(1)（局部分裂）
跳表	概率平衡	中等	0 次（无旋转）

疑惑：AVL 查询更快，为什么 JDK 选红黑树？

论证：HashMap、TreeMap、Linux 进程调度（CFS）、Linux 红黑树内核库……几乎所有"主流红黑树场景"，都是写多读多混合负载。AVL 严格平衡导致频繁旋转——写入开销大；而红黑树最多旋转 3 次就能达到平衡，写入摊还代价更低。

结论：红黑树是"读写权衡的最优解"——查询稍慢于 AVL，但写入快得多。这是 Java 集合、Linux 内核、C++ STL 集体押宝红黑树的根本理由。

2.3 选型决策路径

把"有序 Map 选型"画成决策树：

 ┌─────────────────────────┐
 │  我需要"按 key 有序"吗？│
 └─────────┬───────────────┘
           │
        ┌──┴──┐
        ↓ 否  ↓ 是
   HashMap   ┌─────────────────────────────┐
             │  我需要并发吗？              │
             └──────┬──────────────────────┘
                    │
                 ┌──┴──┐
                 ↓ 否  ↓ 是
            TreeMap   ┌─────────────────────────┐
                      │  写入压力高吗？(>1k QPS) │
                      └──────┬──────────────────┘
                             │
                          ┌──┴──┐
                          ↓ 否  ↓ 是
              synchronizedSortedMap   ConcurrentSkipListMap
              (低并发兼容)            (高并发首选)

结论：选有序 Map 时永远先问"是否要并发"——这一个问题就把候选范围缩到 1~2 个。这与第 4 篇 HashMap 选型决策路径同构。

3. 红黑树五大性质

3.1 性质条文逐条

红黑树的 5 大性质（Cormen 在《算法导论》里的经典定义）：

性质 1：每个节点要么红色要么黑色
性质 2：根节点是黑色
性质 3：每个叶子节点（NIL，即空节点）是黑色
性质 4：红色节点的两个子节点都是黑色（红节点不能连续）
性质 5：从任一节点到其每个叶子的所有简单路径上，黑色节点数相同

疑惑：为什么是这 5 条？少一条会怎样？

论证——逐条删去验证必要性：

• 删性质 1（每个节点必须有颜色）：红黑性质本身就消失了，平衡机制崩塌。
• 删性质 2（根必须黑）：插入时需要对根的颜色单独讨论，且根可能与子节点形成红红冲突——简化用，可去除但增加代码复杂度。
• 删性质 3（NIL 是黑色）：黑高定义中"包不包括 NIL"会产生歧义，删除调整时无法对叶子做颜色判断——算法不可去。
• 删性质 4（红不连续）：黑高相同的前提下，最长路径可以无限长——O(log n) 保证消失。
• 删性质 5（黑高相等）：树可以严重不平衡——O(log n) 保证消失。

结论：性质 4 和性质 5 是 "O(log n) 保证的两条腿"——缺一不可。性质 1、2、3 是辅助性约束，让算法实现得以简化和明确。

3.2 黑高与最长路径

核心定理：红黑树最长路径 ≤ 最短路径的 2 倍。

证明思路：

设黑高 (black height) = bh
最短路径：全是黑节点，长度 = bh
最长路径：黑红交替，长度 = 2*bh （红黑红黑...红黑）
                                 ↑
                              性质 4 限制：红不能连续
                              所以红节点最多与黑节点 1:1

视觉对比：

最短路径 (全黑):                  最长路径 (黑红交替):
                                
        [B]                              [B]
         │                                │
        [B]                              [R]
         │                                │
        [B]                              [B]
         │                                │
        [NIL]                            [R]
                                          │
                                         [B]
                                          │
                                         [NIL]
        长度 = 3                        长度 = 6 = 2 * 3

结论：性质 4 + 性质 5 保证树高 ≤ 2·log₂(n+1) ——这就是 O(log n) 时间复杂度的数学根基。换句话说，红黑树比最优 BST 最多深一倍，但代价是写入旋转少得多。

3.3 性质保证的本质

跳出条文看本质——红黑树 5 大性质的设计哲学：

哲学 1：用颜色编码"局部不平衡度"： 红节点像"减震器"——允许短期容忍局部高度差异，避免每次插入都必须严格再平衡（如 AVL 那样）。这是**用空间（颜色位）换时间（旋转次数）**的经典权衡。

哲学 2：约束本身是对称的： 所有性质都不区分左右子树——左旋右旋互为对偶。这让算法实现可以对称简化（每个调整规则的"左父亲"版本翻转就能处理"右父亲"版本）。

哲学 3：不严格、但可验证： 红黑树不是"最平衡"的——AVL 比它更平衡。但红黑性质容易在 O(1) 局部检查（看节点颜色即可），AVL 必须计算左右子树高度差（需要额外字段）。性质 4 + 5 用最少的状态信息表达了"近似平衡"。

结论：红黑性质是"工程化的平衡定义"——不追求极致平衡，但追求用最少的额外存储和最少的调整次数逼近平衡。这与 §17 篇 GC "近似最优"的哲学是同一思想——完美的敌人是足够好。

4. 节点结构剖析

4.1 Entry 字段布局

TreeMap 的内部节点 TreeMap.Entry：

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;          // ★ 父指针
    boolean color = BLACK;      // ★ 颜色 (true=BLACK, false=RED)
    
    // 构造、equals、hashCode...
}

6 个字段的内存布局（64 位 JVM、UseCompressedOops）：

Entry 对象布局
┌──────────────────────────────────────────┐
│ Mark Word         (8B)                   │  对象头
│ Klass Ptr         (4B)                   │  类型指针 (压缩)
│ key 引用          (4B)                   │
│ value 引用        (4B)                   │
│ left 引用         (4B)                   │
│ right 引用        (4B)                   │
│ parent 引用       (4B)                   │
│ color             (1B + 7B padding)      │  ★ 颜色独占 8B（对齐填充）
└──────────────────────────────────────────┘
总大小：48B/节点

对比 HashMap.Node（无 parent、无 color）：32B/节点。TreeMap 节点比 HashMap 节点多 50% 空间——这是 TreeMap 的固定空间代价。

4.2 颜色位的存放

疑惑：颜色只有红/黑两种状态，1 个 bit 就够，为什么用 1 个 boolean（占 8B）？

论证：JVM 没有"位字段"概念——任何字段最少 1 字节（boolean 实际占 1 字节）+ 对齐填充。所以"1 bit 颜色"在 JVM 里实际占 8B。

有没有更紧凑的方案？有！Linux 内核红黑树（include/linux/rbtree.h）把颜色位塞进了 parent 指针的最低位：

struct rb_node {
    unsigned long  __rb_parent_color;   /* 高位是 parent 指针，最低位是颜色 */
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};

由于 64 位指针地址对齐，最低 3 位永远是 0——可以"借"最低 1 位放颜色。这样每个节点省 8B。但 Java 没有这种位运算指针——JVM 抽象层屏蔽了这种 hack 的可能。

结论：TreeMap 的"颜色单独占 8B"是 JVM 抽象层带来的不可消除开销。这也是为什么 §20 篇 ConcurrentHashMap 的 TreeNode 比 Node 大近一倍——红黑树的固定空间代价。

4.3 父指针的代价

疑惑：BST 需要父指针吗？只有左右孩子也能查找。

论证：父指针的主要用途有 3 个：

1. 插入后向上回溯调整：插入新节点后，需要从插入点向上检查"红红冲突"——没有 parent 就只能用栈记录路径
2. 删除后双黑修复：删除时要从删除点向上回溯修复双黑——同样需要 parent
3. 后继/前驱查找：找一个节点的后继（比它大的最小节点）需要向上找祖先——需要 parent

代价：每节点多 4B 引用 + GC root 扫描时间增加（红黑树是双向引用，GC 不能用简单的子树扫描）。

结论：parent 指针是红黑树为"O(log n) 调整"必须付出的空间代价。这与第 19 篇 LinkedList 的 prev 指针同源——都是"为了快速向前回溯"付出的固定开销。

5. 旋转操作根基

5.1 左旋几何直觉

旋转是平衡树调整的物理工具——它改变树的形状但保持 BST 性质。

左旋（Left Rotate）——以节点 X 为支点，把 X 的右子节点 Y 提升到 X 的位置：

左旋前               左旋后
                              
    X                    Y
   / \                  / \
  α   Y         ─→     X   γ
     / \              / \
    β   γ            α   β

关键不变式：中序遍历顺序不变（α < X < β < Y < γ 在前后保持一致）。

源码（TreeMap.rotateLeft）：

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;          // r = Y
        p.right = r.left;                // X.right = β
        if (r.left != null)
            r.left.parent = p;           // β.parent = X
        r.parent = p.parent;             // Y.parent = X.parent
        if (p.parent == null)
            root = r;                    // 若 X 是根，Y 成为新根
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;                      // X 成为 Y 的左孩子
        p.parent = r;                    // X.parent = Y
    }
}

关键观察：左旋只动 6 条边的连接——是 O(1) 局部操作。这是红黑树能做到 O(log n) 的关键之一：调整局部，不重建全树。

5.2 右旋几何直觉

右旋（Right Rotate） 是左旋的对偶——以节点 Y 为支点，把 Y 的左子节点 X 提升：

右旋前               右旋后
                              
      Y                X
     / \              / \
    X   γ      ─→    α   Y
   / \                  / \
  α   β                β   γ

对称性：右旋的代码与左旋完全镜像——只需把所有 left 改成 right、right 改成 left 即可。

结论：红黑树所有调整规则都成对出现（叔叔在左 vs 叔叔在右、删除黑兄在左 vs 黑兄在右）——这就是为什么 5 大性质必须左右对称。对称性是简化算法实现的必要条件。

5.3 旋转的不变式

旋转操作必须满足三个不变式：

不变式 1：BST 性质保持
        左子树 < 节点 < 右子树
        
不变式 2：中序遍历不变
        旋转前后，按 key 升序遍历的结果完全一致
        
不变式 3：旋转节点和其参与的子树外部，整棵树结构不变
        旋转是"局部操作"

疑惑：旋转会改变颜色吗？

论证：旋转本身不改颜色——只改指针。但调整算法常常"先重染色再旋转"：先把节点染色，再用旋转把"性质 5（黑高相等）"恢复。

结论：旋转是"形状调整"，染色是"颜色调整"——两者配合，红黑树才能在 O(log n) 内恢复全部 5 大性质。这是第 6、7 章插入/删除调整的内核。

6. 插入调整规则

6.1 五种局面分类

新插入节点永远染成红色（为什么？因为染红只可能违反性质 4，而染黑会违反性质 5——性质 4 比性质 5 容易修复）。

新节点 N 插入后，按"父亲、叔叔、爷爷"的颜色与位置分 5 种局面：

局面 0：N 是根节点              → 直接染黑（结束）
局面 1：N 的父亲是黑色          → 不违反任何性质（结束）
局面 2：父红 + 叔红              → 重染色 + 上溯（递归）
局面 3：父红 + 叔黑 + N 与父同侧  → 染色 + 单旋（结束）
局面 4：父红 + 叔黑 + N 与父异侧  → 双旋（结束）

总结：5 种局面中——只有局面 2 需要递归向上，其余 4 种局部解决。这就是为什么红黑树插入最多 O(log n) 次重染色 + 最多 2 次旋转——递归向上次数最多 = 树高。

6.2 叔叔红色情形

局面 2：父红 + 叔红：

插入前                                   调整后
        [G]B                                  [G]R    ← 染红
       /    \                                /    \
     [P]R   [U]R                           [P]B   [U]B  ← 染黑
      │                                      │
     [N]R  ← 新插入红节点                    [N]R
     
     P.color = R, U.color = R               G 变红，可能违反"性质 2 (根黑)"
     违反"性质 4 (红不连续)"                 或与 G 的父亲产生新红红冲突
                                           ↓
                                           递归向上把 G 当作"新插入"继续修复

疑惑：为什么叔叔红色就染色不旋转？

论证：当父亲和叔叔都是红色时，爷爷一定是黑色（性质 4）。把父亲、叔叔染黑、爷爷染红——这一步操作：

• 性质 4 在 P-N 处恢复（因为 P 变黑了）
• 性质 5 不变（G 这一层从黑变红，但 P 和 U 都从红变黑，黑节点数差额抵消）

唯一副作用：G 可能与它的父亲形成新的红红冲突——但这是"上溯一层"递归就能处理的。

结论：局面 2 是唯一会上溯的局面——意味着插入调整的递归深度 ≤ 树高 = O(log n)。

6.3 叔叔黑色情形

局面 3：父红 + 叔黑 + N 与父同侧（如均为左子）：

        [G]B                       [P]B    ← 染黑
       /    \                     /    \
     [P]R   [U]B    ─染色─→     [N]R    [G]R  ← 染红
     /                          \         \
   [N]R                          β         [U]B
                       ─右旋(G)─→         

调整步骤：

1. P 染黑、G 染红
2. 以 G 为支点右旋

结果：性质 4 恢复（P 是黑），性质 5 保持（旋转前后黑高一致）。结束，不需要上溯。

局面 4：父红 + 叔黑 + N 与父异侧（如 P 是左子但 N 是右子）：

先左旋 P，转化为局面 3
        [G]B                 [G]B
       /    \              /    \
     [P]R   [U]B  ─左旋─→ [N]R   [U]B
       \                  /
       [N]R             [P]R
                        ↓
                    转入局面 3 处理

结论：局面 4 = "1 次左旋（先把异侧拉回同侧）+ 局面 3"——所以插入最多 2 次旋转。

核心结论：红黑树插入最多 2 次旋转 + O(log n) 次重染色。这是常数级的旋转开销，是它写入快于 AVL 的根本原因。

6.4 完整插入示例

依次插入 10、20、30、15、25、5、12——观察红黑树的变化：

插入 10:
    [10]B   ← 根节点直接染黑

插入 20:
    [10]B
        \
        [20]R   ← 父黑，无需调整

插入 30:
    [10]B                   [20]B    ← 局面 4 → 局面 3
        \                  /    \
        [20]R   ─调整─→  [10]R  [30]R
            \
            [30]R          
    
    20 染黑、10 染红、对 10 左旋

插入 15:
    [20]B
   /    \
  [10]R [30]R
      \
      [15]R    ← 父红叔红 → 局面 2
                10 染黑、30 染黑、20 染红（但 20 是根，再染黑）

    [20]B           ← 根永远黑
   /    \
  [10]B [30]B
      \
      [15]R

插入 25:    
    [20]B
   /    \
  [10]B [30]B
      \  /
   [15]R [25]R   ← 父黑直接插入

插入 5:
    [20]B
   /    \
  [10]B [30]B
  /  \   /
[5]R [15]R [25]R   ← 父黑直接插入

插入 12:   局面 2  →  10 染黑、15 染黑、12 直接插（父红叔红向上染色）
                       12 没有叔叔节点(NIL)，按 NIL=黑处理
                       
    [20]B
   /    \
  [10]B [30]B
  /  \   /
[5]R [15]R [25]R
     /
    [12]R       ← 等等，父叔关系：12 的父是 15(R)，叔是 5(R)
                   局面 2：12 父红叔红 → 5、15 染黑，10 染红
                   
    [20]B
   /    \
  [10]R [30]B
  /  \   /
[5]B [15]B [25]R
     /
    [12]R
                   10 父亲是 20(B)，无新冲突，结束

结论：完整 7 次插入只触发了 1 次旋转和 4 次重染色——远低于 AVL 的旋转频率。这个例子直观展示了"红黑树用染色减少旋转"的设计哲学。

7. 删除调整规则

7.1 删除的本质

BST 删除有 3 种情况：

情况 A：删除节点是叶子          → 直接删除
情况 B：删除节点只有 1 个孩子    → 用孩子替换
情况 C：删除节点有 2 个孩子      → 用后继节点替换，转化为情况 A 或 B

红黑树删除的关键：所有删除最终都归结为"删除一个最多有 1 个孩子的节点"——情况 C 用"后继替身"技巧转化。

TreeMap.deleteEntry 源码片段：

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    if (p.left != null && p.right != null) {       // ← 情况 C
        Entry<K,V> s = successor(p);                // 找后继节点
        p.key = s.key;                              // ★ 偷梁换柱：把后继的 key/value 复制到 p
        p.value = s.value;
        p = s;                                      // 转而删除后继
    }
    
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
    if (replacement != null) {                     // ← 情况 B
        // ... 用孩子替换
        if (p.color == BLACK)
            fixAfterDeletion(replacement);          // ★ 双黑修复
    }
    // ...
}

关键技巧：情况 C 用"复制 key/value、删除后继"——避免移动整个节点。但代价是外部引用此节点的代码会突然看到不同的 key——这是 TreeMap 删除时不能向外暴露 Entry 引用的根本原因。

7.2 双黑节点危机

疑惑：为什么删除黑色节点要"修复"？

论证：删除一个黑色节点会让该路径黑高 -1——违反性质 5。

删除前                          删除后
        [P]                          [P]
       /                            /
     [B]B   ← 要删的黑节点       [N]
     /
   [N]                              黑高从 2 变成 1
                                    其他路径黑高仍是 2
                                    ★ 性质 5 被破坏

解决方案：把替换节点 N 临时染成"双黑" ——视为额外多了一层黑色——然后通过旋转和染色把"多出的黑"消化掉或上推到根（被根吃掉）。

双黑修复的目标：不破坏其他性质的前提下，把"多余的黑"消除。

7.3 四种修复局面

设要修复的双黑节点是 N，N 的兄弟是 S，按 S 及其子节点颜色分 4 种局面（左对称版）：

局面	兄弟 S	S 的左子	S 的右子	处理
1	红	黑	黑	兄弟染黑、父染红、对父左旋 → 转入其他局面
2	黑	黑	黑	兄弟染红、双黑上推到父 → 递归
3	黑	红	黑	兄弟与左子互换颜色、对兄弟右旋 → 转入局面 4
4	黑	任意	红	兄弟染父色、父染黑、S 右子染黑、对父左旋 → 结束

关键观察：只有局面 2 会向上递归（与插入对称——只有"上邻全红"时才递归）。其他 3 种局部解决。

结论：红黑树删除最多 3 次旋转 + O(log n) 次染色。这是个相对复杂的算法，但摊还代价仍是 O(log n)——每次删除的旋转常数项 ≤ 3。

与插入对比：

操作	最多旋转	最多上溯次数	复杂度
插入	2 次	O(log n)	O(log n)
删除	3 次	O(log n)	O(log n)
查询	0 次	0	O(log n)

红黑树是"读 0 旋、写 ≤3 旋"——这个常数级旋转上限是它击败 AVL 的关键。

8. 跳表对比分析

8.1 跳表结构原理

跳表（Skip List）是 William Pugh 1989 年提出的——用概率代替平衡的数据结构。

Level 3:  [HEAD] ─────────────────────────────────→ [50] ──→ NIL
                                                     │
Level 2:  [HEAD] ──────────→ [20] ────────────────→ [50] ──→ NIL
                              │                      │
Level 1:  [HEAD] ──→ [10] ──→ [20] ──→ [30] ──→ [40] [50] ──→ NIL
                      │        │        │        │   │
Level 0:  [HEAD] ──→ [10] ──→ [20] ──→ [30] ──→ [40] [50] ──→ NIL

核心思想：

• 底层是有序链表——存全部数据
• 上层是"快速通道"——每个元素以 1/2 概率出现在上一层
• 查询从最高层开始向右走，遇到比目标大的节点就下降一层

期望复杂度：高度 ≈ log n，每层移动 O(1) 步 → 总 O(log n)。

疑惑：跳表用概率，会有"运气差"的情况吗？

论证：跳表的高度 H 服从几何分布——P(H > k) = (1/2)^k。即：

• P(H > 32) < 1/4×10⁹（亿分之一）
• P(H > 64) ≈ 0（数学上几乎不可能）

跳表用 1024 个节点时，期望高度 ≈ 10，最多到 32 层就几乎封顶。在工程上，用一个固定的 32 层数组就足够覆盖 2^32 个元素——这是跳表能在工程上实用的根本原因。

结论：跳表用"概率平衡"代替"严格平衡"——牺牲一点最坏情况（低概率退化）换取算法极简、并发友好。

8.2 复杂度对比

维度	红黑树	跳表
查询	O(log n) 严格	O(log n) 期望
插入	O(log n) + ≤2 旋转	O(log n) + 0 旋转
删除	O(log n) + ≤3 旋转	O(log n) + 0 旋转
空间	n × 48B	n × ~32B（期望）
缓存友好	一般（指针跳跃）	较差（更多指针）
并发友好	极差（全局回溯）	优秀（局部 CAS）
实现复杂度	极高（5 种局面）	中等

关键差距：并发友好性——红黑树的"自下而上回溯调整"在并发下是噩梦；跳表的所有操作只动自己的指针，CAS 即可完成。

8.3 并发友好性

疑惑：为什么跳表能并发而红黑树不能？

论证——看插入操作的"修改范围"：

红黑树插入 30 (假设触发 1 次旋转 + 染色上溯 3 层):
  修改：
    新节点 N（添加）
    父节点 P（指针 + 颜色）
    叔叔 U（颜色）
    爷爷 G（颜色）
    曾爷爷指针（旋转）
    根节点（可能颜色）
  ★ 6 个节点 + 跨越 3~4 层的指针
  并发场景：必然与其他写线程冲突

跳表插入 30 (假设落在 3 层):
  修改：
    新节点 N（添加，3 层）
    Level 0 前驱.next = N
    Level 1 前驱.next = N
    Level 2 前驱.next = N
  ★ 3~4 个节点的"单链表插入"
  并发场景：每层独立 CAS，互不影响

结论：跳表的修改范围是"局部、可分层独立"的——这是 CAS 友好的本质。红黑树的修改范围是"自下而上、跨层耦合"的——CAS 无法表达这种"事务性"操作。

这就引出了第 9 章的核心论点——ConcurrentSkipListMap 选跳表，是被红黑树的"耦合修改"逼出来的。

9. ConcurrentSkipListMap

9.1 为什么不用红黑树

回到本篇 §1.2 的灵魂问题——JDK 为什么不做"ConcurrentTreeMap"？三个根本原因：

原因 1：旋转操作无法 CAS 化： 红黑树的旋转要原子修改 6 条边——CAS 只能原子修改一个字段。要么用 STM（软件事务内存，JVM 不支持），要么加锁（违背并发设计初衷）。

原因 2：自下而上回溯路径冲突： 两个线程在不同子树插入，但都要回溯到根——根附近必然冲突。冲突频率与树高成正比，n 越大冲突越严重。

原因 3：并发下树不能"折叠/收缩"： 红黑树有"自我收缩"行为（删除节点导致双黑修复，可能让树高 -1）——并发场景下其他线程正在该路径读取，收缩会让它们读到悬空指针。

结论：红黑树的"动态形变"与"无锁并发"是天然冲突的——这就是为什么 Doug Lea 在 JDK 1.6（2007）专门基于跳表实现了 ConcurrentSkipListMap，而不是把 TreeMap 改成线程安全。选错数据结构，再多努力也救不回来——这条工程铁律在数据结构选型上同样成立。

9.2 跳表的无锁化

ConcurrentSkipListMap 的核心是每层独立 CAS：

// 简化版的跳表 put
public V put(K key, V value) {
    Node<K,V> z = new Node<>(key, value, null);
    
    // 1. 找到每层应该插入的位置 (无锁查找)
    Node<K,V>[] preds = findPredecessors(key);
    
    // 2. 自底向上 CAS 插入每层
    for (int level = 0; level < z.height; level++) {
        Node<K,V> pred = preds[level];
        Node<K,V> succ = pred.next[level];
        z.next[level] = succ;
        if (!pred.next[level].compareAndSet(succ, z)) {
            // CAS 失败 → 重新找前驱 → 重试
        }
    }
    return null;
}

关键设计：

1. 底层先插入，上层后插入——保证读线程要么看到完整的多层节点，要么看到只有底层（依然能搜到）
2. CAS 失败重试，不阻塞——读永远不被写阻塞
3. 节点删除用"标记法"——先标记 next 为"逻辑删除"（特殊节点），再物理摘除

结论：跳表的"分层无锁化"是**"乐观并发的天花板"**——它把红黑树"全树原子操作"的难题降维到"每层链表 CAS"。这与第 20 篇 ConcurrentHashMap 的"桶级锁化"思路一脉相承——把全局问题降维到局部问题。

9.3 三大有序 Map 对比

┌─────────────────────────────────────────────────────────────────┐
│ 性能对比 (1000 万元素插入 + 查询)                                │
├──────────────────────────┬──────────────┬───────────────────────┤
│ 容器                      │ 单线程吞吐    │ 16 线程吞吐            │
├──────────────────────────┼──────────────┼───────────────────────┤
│ TreeMap                   │ 1.0x (基准)  │ N/A (非线程安全)       │
│ synchronizedSortedMap     │ 0.85x        │ 0.6x (锁竞争)         │
│ ConcurrentSkipListMap     │ 0.7x         │ 8.5x (近线性扩展)      │
│ ConcurrentHashMap         │ 0.95x        │ 12x (无序，参考值)     │
└──────────────────────────┴──────────────┴───────────────────────┘

结论：

• 单线程：TreeMap > ConcurrentSkipListMap（红黑树常数小）
• 多线程：ConcurrentSkipListMap >> 加锁的 TreeMap

这是为什么"有序 + 并发"场景必选 ConcurrentSkipListMap，没有第二选项。

10. 综合案例串讲

10.1 排行榜真相揭晓

回到第 1 章的电商排行榜，逐条揭晓：

① 红黑树的 5 大性质分别是什么，为什么这 5 条能保证 O(log n)：5 大性质即：节点红或黑、根黑、叶子(NIL)黑、红节点子节点黑、任一节点到所有叶子的简单路径上黑节点数相同。其中性质 4（红不连续）+ 性质 5（黑高相等）是 "O(log n) 的两条腿"——两者共同保证最长路径 ≤ 最短路径 2 倍（§3.2）。其余 3 条是辅助约束。

② 黑高与最长路径：黑高 = 从某节点到任一叶子的黑节点数。最短路径全黑 = bh，最长路径黑红交替 = 2·bh——所以树高 ≤ 2·log₂(n+1)（§3.2）。这就是 O(log n) 的数学根基。

③ 插入调整最多旋转几次，删除调整呢，复杂度的常数项：插入最多 2 次旋转 + O(log n) 次重染色（§6.3）；删除最多 3 次旋转 + O(log n) 次重染色（§7.3）。常数级旋转是红黑树击败 AVL 的关键——AVL 旋转次数随树高增长，而红黑树旋转次数固定。

④ 旋转操作怎么保证 BST 性质不变，左旋右旋怎么对偶：旋转的核心不变式是中序遍历不变——前后元素顺序完全一致（§5.3）。左旋和右旋的代码完全镜像（把所有 left/right 互换即可），这种对偶性保证了所有调整规则都成对出现，简化了算法实现。

⑤ 跳表与红黑树相比的取舍：红黑树查询稍快（严格 O(log n)、无概率），跳表写入稍快（无旋转）；但最关键差异是并发友好性——跳表分层 CAS 友好，红黑树自下而上回溯无法 CAS 化。空间上跳表期望约 ~32B/节点（仅有 next 数组），红黑树固定 48B/节点。

⑥ ConcurrentSkipListMap 为什么不基于红黑树：三个根本原因——红黑树旋转要原子改 6 条边（CAS 不可达）、自下而上回溯导致根部冲突、删除导致树自我收缩与并发读冲突（§9.1）。红黑树的"动态形变"与"无锁并发"天然冲突——这是数据结构选型层面无法补救的硬伤。

⑦ 三大有序 Map 怎么选：单线程默认 TreeMap；高并发选 ConcurrentSkipListMap；老代码兼容时退而求其次用 synchronizedSortedMap。永远先问"是否要并发"——这一个问题就把候选范围缩到 1~2 个（§2.3）。

排行榜延迟翻车的真相：流量翻倍后，某些热点 score 段（如 100 分附近）大量用户集中——TreeMap 的某个分支变得很深，加上 GC 不友好（红黑树的 parent 指针让 G1 写屏障频繁触发）。换成 ConcurrentSkipListMap 后并发读写不再阻塞、节点更小，P99 从 50ms 降到 0.8ms。

10.2 一次 put 的红黑路径

把 treeMap.put(15, "value") 这行的完整链路串起来——回扣本册前 20 篇：

T 0     put(15, "value") 调用
        [13篇] invokevirtual TreeMap.put
        
T+5ns   compare(key, root.key)
        [13篇] 接口分派到 Comparator 或自然顺序 compareTo
        
T+10ns  从根开始向下查找插入位置
        [01篇] 节点对象在堆中，遍历访问触发 cache miss
        红黑树指针密集，缓存友好性一般
        
T+50ns  找到插入位置（叶子）
        new Entry(15, "value", parent)  ← 染红
        [16篇] 新对象在 Eden 区分配
        
T+55ns  从插入点向上检查局面
        [§6.1] 5 种局面分类
        
T+60ns  假设触发局面 2（父红叔红）
        重染色：父黑、叔黑、爷红
        [§6.2] 上溯到爷爷继续检查
        
T+65ns  上溯到根之前，触发局面 4（父红叔黑、N 与父异侧）
        ① 先左旋 P  ← 转化为局面 3
        ② 再右旋 G  ← 完成调整
        [§5.1] rotateLeft 修改 6 条边
        
T+70ns  最终染色：根永远黑
        modCount++  size++
        [19篇] 与 ArrayList 的 modCount 同源 fail-fast
        
T+75ns  put 返回旧值（如果 key 已存在）
        
GC 视角：
        [16篇] Entry 对象在 Eden 区
        [17篇] G1 SATB 写屏障：因为 parent 指针修改，
              引发"老→新"跨代引用记录到 RememberedSet
              ★ 红黑树写屏障开销比 HashMap 高
        
JIT 视角：
        [14篇] put 是热点方法，C2 编译为机器码
        compareTo 内联，旋转操作也被内联
        但旋转分支多，难以被向量化优化
        
并发视角：
        [20篇] TreeMap 不是线程安全的
        多线程 put 会破坏 BST 性质（指针错乱）
        必须用 ConcurrentSkipListMap

这条时间线串起本篇的关键概念——一行普通的 put 背后，是 BST 查找、5 种局面分类、染色与旋转的精密配合。

10.3 设计哲学回扣

跳出技术细节，提炼三条贯穿红黑树设计的工程哲学：

1. "近似平衡"优于"严格平衡"：红黑树不是 AVL 那样的严格平衡——但常数级的旋转（≤3 次）让写入速度反超 AVL。这条原则在 GC（§17 G1 自适应步长）、并发计数（§9.1 LongAdder 弱一致 sum）、HashMap 树化阈值（§20 阈值 8 是概率门槛而非严格阈值）等多处都有体现——完美的敌人是足够好。

2. 对称性是简化算法的关键：红黑树的所有调整规则都左右对偶——左旋有右旋、叔叔在左有叔叔在右、双黑兄在左有兄在右。对称性把代码量减半，把心智成本减半。这与 §5 篇 String 的不可变设计、§19 篇 Iterator 的统一契约一脉相承——好的抽象总是对称的。

3. 数据结构与并发模型是耦合选择：红黑树的"动态形变"决定了它必然是单线程数据结构；跳表的"分层独立"决定了它天生适合 CAS。选数据结构就是选并发模型——这条原则解释了为什么 §20 篇的 ConcurrentHashMap 不基于 TreeMap、为什么本篇的 ConcurrentSkipListMap 不基于红黑树。先想清楚并发场景，再选数据结构，永远不要反过来。

10.4 有序容器速查表

最后一张表——任何有序容器选型 5 秒决策：

业务诉求	推荐	不推荐
单线程有序 Map（默认）	TreeMap	LinkedHashMap (按插入序非按 key 序)
高并发有序 Map	ConcurrentSkipListMap	synchronizedSortedMap
范围查询 (subMap)	TreeMap / CSLM	HashMap (无范围概念)
top-K 查询	TreeMap.firstKey/lastKey	全排序
优先队列（每次取最小）	PriorityQueue (堆)	TreeMap (有更好选择)
有序集合（去重）	TreeSet	List + sort
滑动窗口聚合	TreeMap.subMap	List + filter
区间统计 (count of range)	TreeMap (近似)	树状数组/线段树
并发优先队列	PriorityBlockingQueue	CSLM (高级特性溢出)
老代码兼容	synchronizedSortedMap(TreeMap)	重写

有序容器心法三条：

1. 单线程有序，TreeMap 永远是默认答案
2. 并发有序，ConcurrentSkipListMap 是唯一选择
3. 用 PriorityQueue 而非 TreeMap 实现优先队列（堆比红黑树更适合）

至此第 21 篇完成——我们用 1 万字把红黑树五大性质、插入删除调整、跳表对比、ConcurrentSkipListMap 设计哲学讲透。但 Map 家族还有一员——LinkedHashMap 凭什么能既保插入序又支持 LRU？下一篇我们顺着"为什么 LinkedHashMap 既是 Map 又是双向链表"这条线，进入 第 22 篇：LinkedHashMap与LRU实现——把 access-order/insertion-order 双模式、removeEldestEntry 钩子、Caffeine 高级 LRU 一次讲透。