二叉搜索树的查找代价取决于树高，而树高由插入顺序决定：同一批键按升序写入就会退化成链表。红黑树用五条约束加常数次旋转把最坏树高钉在 O(log n)；理解它的最短路径是翻译成 2-3-4 树——红链接表示"两层本是一个节点"。
1. 退化：树高由谁决定
有序插入、单调数据（自增主键、时间戳）加上没有自平衡约束，每次插入都挂在最右子树上，树高等于键数。
static Node insert(Node root, int k) {
if (root == null) return new Node(k);
if (k < root.key) root.left = insert(root.left, k);
else root.right = insert(root.right, k); // 升序时永远走这一支
return root;
}
查找从"每层砍一半"变成"每层只走一步"，典型量级由 O(log n) 掉到 O(n)；递归深度也等于 n，StackOverflowError 常先于变慢暴露。
2. 五条性质，每条在防什么
| # | 性质 | 在保证什么 |
|---|---|---|
| 1 | 节点非红即黑 | 提供一个比特的信用额度：红节点是"预支的高度" |
| 2 | 根为黑 | 给黑高一个统一起点，省掉根为红的分支讨论 |
| 3 | 红节点的子节点必须为黑 | 锁死最长路径，任何路径不会比另一条长一倍以上 |
| 4 | 任一节点到其所有叶子的路径黑节点数相同 | 黑高相等，等价于 2-3-4 树的完全平衡 |
| 5 | 叶子（NIL 空指针）视为黑 | 让"每条路径黑数相同"在任意节点上都可归纳 |
性质 3 限制最长能多长，性质 4 保证最短不会太短，合起来才推出 h ≤ 2*log2(n+1)。新节点先染红：染红只违反性质 3 或 2，局部可修。
static final boolean RED = false, BLACK = true;
static class Node<K, V> {
K key; V value;
Node<K, V> left, right, parent;
boolean color = RED; // 新插入先染红，不动黑高
}
3. 与 2-3-4 树的一一对应
2-3-4 树允许一个节点存 1–3 个键（2/3/4 节点），所有叶子同层。红黑树的翻译规则只有一条：红链接表示孩子与父同属一个 2-3-4 节点，把两层压成一层。
| 红黑树形态 | 2-3-4 节点 | 键数 |
|---|---|---|
| 黑节点，无红子 | 2 节点 | 1 |
| 黑节点 + 一个红子 | 3 节点 | 2 |
| 黑节点 + 左右各一红子 | 4 节点 | 3 |
| 红黑树黑高 | 2-3-4 树的树高 | — |
黑高相等即所有叶子同层：4 节点该分裂时表现为叔叔为红的变色，该旋转时表现为叔叔为黑。
4. 插入修复：三种情形
流程固定：按 BST 找位置 → 染红 → 向上修复，只关心叔叔颜色、是否同侧、祖父。
| 情形 | 条件（P 父 / U 叔 / G 祖 / N 新） | 动作 | 本质 |
|---|---|---|---|
| 变色 | U 为红 | P、U 染黑，G 染红，N 跳到 G 继续 | 4 节点分裂，键上移 |
| LL / RR | U 为黑且同侧 | 单旋 G，P 黑 G 红 | 形成 3 节点，一次旋转 |
| LR / RL | U 为黑且异侧 | 先旋 P 掰直，退化成上一种 | 两次旋转 |
private void fixAfterInsert(Node n) {
n.color = RED;
while (n != root && colorOf(parentOf(n)) == RED) {
Node p = parentOf(n), g = parentOf(p);
if (p == leftOf(g)) {
Node u = rightOf(g); // 叔叔
if (colorOf(u) == RED) { // 情形 1：变色，可能向上传播
setColor(p, BLACK); setColor(u, BLACK); setColor(g, RED);
n = g;
} else {
if (n == rightOf(p)) { n = p; rotateLeft(n); } // 情形 3：LR 掰直
setColor(parentOf(n), BLACK); // 情形 2：LL
setColor(parentOf(parentOf(n)), RED);
rotateRight(parentOf(parentOf(n)));
}
} else { /* 右子树镜像：RR / RL，代码对称 */ }
}
root.color = BLACK; // 性质 2
}
一句话：插入最多两次旋转、变色均摊常数——"平衡的代价"就是靠这个被压到极小的。
5. 删除为什么难一个量级
删掉黑节点会破坏性质 4。为了仍用一个颜色位表达状态，就把"缺一个黑"的债务记在孩子身上，称双黑；修复就是向上借或与兄弟合并。
| 情形 | 条件 | 动作 |
|---|---|---|
| 删红叶子 | 直接摘 | 不影响黑高，无需修复 |
| 兄弟为红 | 兄弟红 | 旋转变色，转成兄弟为黑 |
| 兄弟黑且两子皆黑 | 借不到 | 兄弟染红，债务上移 |
| 兄弟黑且有一红子 | 可借 | 旋转变色，债务清零 |
// 先按 BST 摘下（有两个孩子时改删后继），再统一修复
private void fixAfterDelete(Node x) {
while (x != root && colorOf(x) == BLACK) {
Node s = rightOf(parentOf(x)); // 兄弟
if (colorOf(s) == RED) { // 兄弟红 → 转成黑兄弟
setColor(s, BLACK); setColor(parentOf(x), RED);
rotateLeft(parentOf(x)); s = rightOf(parentOf(x));
}
if (colorOf(leftOf(s)) == BLACK && colorOf(rightOf(s)) == BLACK) {
setColor(s, RED); x = parentOf(x); // 合并，债务上移
} else {
if (colorOf(rightOf(s)) == BLACK) { // 掰直
setColor(leftOf(s), BLACK); setColor(s, RED); rotateRight(s);
s = rightOf(parentOf(x));
}
setColor(s, colorOf(parentOf(x))); // 结算
setColor(parentOf(x), BLACK); setColor(rightOf(s), BLACK);
rotateLeft(parentOf(x)); x = root;
}
}
setColor(x, BLACK);
}
插入只有 3 类情形，删除有 4–6 类且互相嵌套，双黑还可能上移多层。所以实现普遍选"两段式"：先摘节点，再做一次与插入对称的修复。
6. AVL 对照：谁的代价更小
| 维度 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡严格度 | 弱，最长 ≤ 2×最短 | 强，左右高差 ≤ 1 |
| 树高常量 | 约 2*log2(n+1) |
约 1.44*log2(n) |
| 查询代价 | 略高 | 略低 |
| 插入旋转 | 最多 2 次 | 可能沿路径多次 |
| 删除旋转 | 最多 3 次 | 最坏 O(log n) 次 |
| 额外维护 | 一个颜色位 | 高度或平衡因子 |
| 适用场景 | 写频繁、增删为主的内存索引 | 读远多于写、查询延迟敏感 |
差别是常数倍而非量级；决定选型的是旋转次数上界与实现复杂度。
7. TreeMap / TreeSet 与 HashMap 树化
TreeMap 底层是红黑树，Entry 带 color 与 parent。不选 AVL：中序遍历天然有序，subMap/floorKey/ceilingKey 都是 O(log n)，旋转次数有常数上界。迭代器按中序推进，只有结构性修改才失效，遍历顺序也不随扩容变化（HashMap 的顺序会随 resize 改变）。
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(50, "a"); tm.put(20, "b"); tm.put(80, "c");
tm.floorKey(60); // 50，≤60 的最大键
tm.ceilingKey(60); // 80，≥60 的最小键
tm.subMap(20, true, 80, false); // 区间视图，随原表变化，不复制元素
// 只做一次性排序时用 ArrayList + Collections.sort()，比 TreeMap 便宜
HashMap 的桶默认是链表，长度到 8 且容量 ≥ 64 才树化，降到 6 退回链表。
| 参数 | 值 | 机制 |
|---|---|---|
TREEIFY_THRESHOLD |
8 | 哈希良好（λ≈0.5）时长到 8 的概率已极低，只在分布异常时树化 |
UNTREEIFY_THRESHOLD |
6 | 与 8 之间留滞后区间，避免在 7 附近来回抖动 |
MIN_TREEIFY_CAPACITY |
64 | 短链表多因表太小，先扩容 |
TreeNode |
继承链表结构 | 多 parent/left/right/red，内存远大于 Node，退化只需拆树关系 |
if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); // 内部再判容量 < 64 则 resize()
树化是给极端碰撞兜底的安全网，不是默认路径。
8. 复杂度汇总
| 结构 | 查找平均 | 查找最坏 | 插入最坏 | 删除最坏 |
|---|---|---|---|---|
| 退化 BST | O(n) |
O(n) |
O(n) |
O(n) |
红黑树 / TreeMap、AVL |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| 跳表（Redis ZSET） | O(log n) 期望 |
同左 | 同左 | 同左 |
| B+ 树（InnoDB） | O(log n) |
O(log n) |
O(log n) |
O(log n) |
后两行按各自口径读：ZSET 是概率期望；InnoDB 的代价主要是随机磁盘 IO 次数，不是内存指针跳转。
9. 排错
| 现象 | 原因 | 处理 |
|---|---|---|
| 有序主键写入后查询变慢 | 自写 BST 退化 | 换 TreeMap 或补平衡 |
迭代时抛 ConcurrentModificationException |
迭代中发生结构性修改 | 用 Iterator.remove()，或先复制键集 |
TreeMap 报 ClassCastException |
键未实现 Comparable，也没传 Comparator |
传比较器 |
| 某桶链表很长，树化没救 | hashCode() 分布差 |
改哈希实现，树化只是兜底 |
TreeMap 做无序缓存，吞吐明显下降 |
为不需要的有序性付了 O(log n) 与对象头开销 |
换 HashMap |
ConcurrentModificationException 与红黑树无关，是迭代器的 modCount 校验。
10. 边界
| 场景 | 首选 | 理由 |
|---|---|---|
| 无序 KV、追吞吐 | HashMap |
O(1) 平均，无旋转与颜色位 |
| 有序 + 范围查询 + 动态增删 | TreeMap |
区间视图与邻键查询是哈希表做不到的 |
| 读极多写极少 | AVL / 静态排序数组 | 树更矮或连续访问，缓存友好 |
| 一次性排序后只查不改 | ArrayList + Collections.sort() |
排序一次，之后二分 O(log n) |
| 并发有序 | ConcurrentSkipListMap |
跳表无旋转；TreeMap 非线程安全 |
| 超大表、磁盘为主 | B+ 树 | 层数少、每层多键，减少随机 IO |
两个越界：TreeMap 不是"最优平衡树"，优化目标是维护成本而非最小树高；它也不线程安全，并发写会读到中间状态。
一句话收束：红黑树是"最坏情况可证 + 维护成本极小"的工程折中，不是平衡度上的最优解。
11. 自测
- 按升序插入 n 个键，普通 BST 的树高是多少？此时什么会先于性能暴露出来？
- 性质 3 与性质 4 各限制什么？为什么只靠其中一条推不出树高上界？
- 翻译成 2-3-4 树时，红链接代表什么？黑高对应哪个量？
- "叔叔为红"与"叔叔为黑"分别做什么？为什么前者会向上传播？
- 删除中的双黑是什么？为什么实现普遍选择先摘节点再重平衡？
HashMap树化阈值为什么是 8，退化阈值为什么是 6 而不是 7？