这一篇在干嘛？
这一章把前面各章的”教学版”升级成”工业版”：STL
map/set真正用的红黑树、随机化平衡的 treap、字符串检索的后缀数组与后缀树、多维空间搜索的 kd 树，以及实践中最快、理论还没完全搞懂的配对堆。学完你就能看懂标准库和数据库索引的真身。
12.1 自顶向下伸展树
第 4 章的伸展树是”先递归找到、再一路旋回”。自顶向下版本在下降过程中就完成旋转（zig/zig-zag/zig-zig），用左树/中树/右树三棵子树的重新拼接实现，一次遍历即完成访问+伸展，不用父指针、不用栈：
白话：把沿途经过的节点拆到”左边小树（都小于目标）“和”右边小树（都大于目标）“，最后三树拼接、目标登顶。摊还性质与自底向上版相同，但实现更快（一次下降）更省（无递归栈）。
12.2 红黑树：STL map 的真身
五条性质：① 每节点红或黑；② 根黑；③ 叶（NULL）黑；④ 红节点的孩子必黑（无红红相邻）；⑤ 根到每片叶的路径黑高相同。可证：高 ≤ 2log(N+1)——平衡保证。
自顶向下插入：一路”翻色”到底
下降途中遇到”双红孩子”就颜色翻转（父变红、子变黑），顺带修复可能的红红冲突；到达底部插入红节点。这样保证到达插入点时不需要回溯——旋转至多一次（局部），无递归回溯。
自顶向下删除：把红送到叶子
删除难点是”删黑节点会破坏黑高”。策略：让下降路径上始终保持”当前节点是红的”——把红情况化归为少数几种局部模式（旋转+翻色），到叶子时删除红节点即可，不破坏任何性质。
白话：红黑树 vs AVL：AVL 更严格平衡（查得略快）、红黑树旋转更少（改得更快），且插入至多 2 次旋转、删除至多 3 次——写库（每次写入都要重平衡）选红黑树。与 AVL 的旋转同构：红黑树的翻色+旋转组合能一一对应到 AVL 的单/双旋转，学会一个另一个自然通。
12.3 Treap：树 + 堆的随机化婚姻
每个节点两个键：搜索键（满足 BST 序）+ 随机优先级（满足堆序：父 < 子）。优先级随机 ⇒ 树形状 = 随机 BST ⇒ 期望高 。插入 = 先按 BST 插入，再用旋转把新节点的优先级”顶”上去（最多 log N 次旋转）。
白话：把”平衡”外包给随机数——优先级是随机的，敌人构造不出坏输入（除非预知你的随机种子）。实现比 AVL/红黑树短一个量级，是算法竞赛里”要平衡树又懒得写红黑树”的标准答案。对偶理解：给每个元素一个随机权重后，treap 是唯一的 Cartesian 树——结构由数据完全确定，这就是它好写的原因。
12.4 后缀数组与后缀树：字符串检索的重炮
后缀：从每个位置开始的尾巴。如 banana 的后缀有 banana, anana, nana, ana, na, a。
后缀数组 SA：把所有后缀排序后的下标数组。banana 的 SA = {5, 3, 1, 0, 4, 2}（a < ana < anana < banana < na < nana）。有了它：
- 子串查询 = 在后缀数组上二分（子串必然是某后缀的前缀）：。
- 相邻后缀的最长公共前缀（LCP）给出重复子串信息—— longest repeated substring、文档比较（diff）、生物序列分析的基础。
构造：朴素排序 ；倍增法 ；原书还讲线性 DC3。要点是”按前 k 个字符的排名做两次基数排序翻倍”。
后缀树：后缀的压缩 trie（公共前缀合并）。deed 的后缀 {d, eed, ed, deed} 的 trie：
查询子串沿树下行 ——比后缀数组还快，代价是内存大（常数 10–20 倍）。Ukkonen 线性构造是字符串算法的巅峰之一。
白话：后缀 = 把字符串”所有可能的查找入口”预先排好队。DNA 测序、全文搜索引擎、代码查重，凡”在长文本里反复找模式”都靠这一族结构。
12.5 kd 树：多维空间里做二分
一维排序能二分查找，二维平面找”最近邻/范围查询”怎么办？2-d 树：偶数层按 x 分裂、奇数层按 y 分裂（kd 树推广到 k 维），建树 ：
白话：kd 树把平面切成嵌套的矩形格子，查询”半径 r 内的点”时只进与之相交的格子——绝大多数分支被整块剪掉。维度 ≤ 20 时实用；维度太高退化（维度灾难），高维近邻搜索转向 LSH/向量索引。
12.6 配对堆（Pairing Heap）：实践最快的堆
结构：多叉树 + 左孩子右兄弟表示。所有操作都极简：insert/deleteMin/decreaseKey 的”整理”推迟到 deleteMin：取走根后，把孩子们的森林两两合并（第一趟）再从右往左收编（第二趟）：
白话：配对堆是”代码 100 行、实测最快、理论没证完”的传奇——decreaseKey 的摊还复杂度至今没有紧界（猜想 O(log log N)）。Dijkstra/Prim 的大规模实现里它是二叉堆和斐波那契堆之外的第三极。
选型总结：有序字典 → 红黑树（通用库）/ treap（自写）/ 伸展树（热点访问）；字符串检索 → 后缀数组（省内存）/ 后缀树（查询快）；空间数据 → kd 树；可合并堆 → 配对堆（实践）/ 二项队列（理论齐整）。
常见坑
① 红黑树删除忘”保持当前红”的不变量：自顶向下删除若中途红变黑，叶子处的情形分析会爆炸——严格按书上的模式走。② treap 插入旋转方向写反：优先级小者在上（小根堆序），新节点向上旋转的方向取决于它和父节点谁的优先级小。③ 后缀数组二分比较：直接比较后缀是 每次比较，必须配合 LCP 信息或预处理，否则复杂度虚高。
通关标准
学完本篇你应该能做到：① 陈述红黑树五性质并解释为什么高 ≤ 2log N；② 描述自顶向下插入的翻色机制；③ 解释 treap 如何用随机优先级获得期望平衡、旋转如何维持双序；④ 手推 banana 的后缀数组并用它做子串二分；⑤ 说出配对堆 deleteMin 的两趟合并流程。
红黑树的"黑高"是什么？它如何给出高度上界？
黑高 = 路径上黑节点数（不含根）。性质⑤保证所有路径黑高相同，性质④保证红不能相邻 ⇒ 每两个黑之间至多插一个红 ⇒ 高 ≤ 2×黑高；而黑高 h 的子树至少含 2^h − 1 个内部节点，故高 ≤ 2log(N+1)。
treap 和"随机插入顺序建 BST"有什么本质区别？
随机顺序 BST 的期望平衡依赖输入到达顺序真随机；treap 的优先级是数据自带的随机属性，插入/删除/合并任意混合操作序列下都保持期望平衡，还能做 split/merge（区间树）这类 AVL 难做的操作。
后缀数组为什么能 O(|P| log N) 查子串？
任意子串必是某个后缀的前缀；后缀已排序，子串查询退化为二分查找（每次比较前缀），比较代价 O(|P|)。配合 LCP 数组可进一步加速到 O(|P| + log N)。
kd 树为什么在维度 > 20 后失效？
剪枝依赖”格子与查询球相交则进入”，维度升高后格子的表面积/体积比暴涨，几乎所有格子都与查询球相交，剪枝失效，退化为近线性扫描（维度灾难）。
配对堆比斐波那契堆慢的理论保证在哪里、快的原因又是什么？
理论上斐波那契堆有 decreaseKey O(1) 的摊还证明，配对堆没有紧界；但配对堆结构扁平、指针少、缓存友好、代码极短，实测（尤其大规模 Dijkstra）往往更快——理论与实践的著名错位。