CLRS 第 20 章问题 20-2 全解析：y-fast trie 的构造、空间压缩与复杂度证明

导读：本文完整解析《算法导论（第三版）》第 20 章章末问题 20-2——D. Willard 提出的 y-fast trie（y 快速树）。该数据结构在大小为 $u$ 的整数全域上，以 $O(n)$ 空间存储 $n$ 个元素，并把 MEMBER、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR 的最坏情形运行时间压到 $O(\lg\lg u)$，把 INSERT、DELETE 做到 $O(\lg\lg u)$ 摊还时间。读完本文，你将掌握 y-fast trie 从"前缀完美哈希 + 双向链表"的初步结构，到"聚类 + 代表 + 红黑树"的空间优化全过程，并能独立复现其全部 8 个子问题的复杂度证明。

---

1. 问题背景：与 van Emde Boas 树同级的查找利器

问题 20-2 开篇即给出 y-fast trie 的性能定位：与 van Emde Boas 树（vEB 树）一样，y-fast trie 对取自规模为 $u$ 的全域中的元素执行 $\text{MEMBER}$、$\text{MINIMUM}$、$\text{MAXIMUM}$、$\text{PREDECESSOR}$、$\text{SUCCESSOR}$ 五种操作，最坏情形时间为 $O(\lg\lg u)$；而 $\text{INSERT}$ 与 $\text{DELETE}$ 需要 $O(\lg\lg u)$ 的摊还时间。

它与 vEB 树最大的差异在于空间开销。标准 vEB 树的存储量依赖于全域大小 $u$（量级为 $O(u)$），而"精简空间的 vEB 树"（reduced-space vEB tree，即 问题 20-1）通过把 cluster 数组换成动态哈希表，把空间降为与已存元素个数 $n$ 相关。y-fast trie 追求同样的目标：只用 $O(n)$ 空间存储 $n$ 个元素。其设计关键支柱是完美哈希（perfect hashing），对应 第 11.5 节。

从仓库目录结构看，docs/Chap20/Problems/20-2.md 与 docs/Chap20/Problems/20-1.md 并列放在第 20 章 Problems 目录下（见 mkdocs.yml 导航配置），两者互为姊妹题：20-1 解决 vEB 树的空间问题，20-2 则给出另一种空间高效、且不支持 O(1) MINIMUM 的折中方案——这正是理解两种"空间压缩思路"的对照素材。

---

2. 初步结构：前缀完美哈希表 + 有序双向链表

在正式引入 y-fast trie 之前，题目先构造一个"过度消耗空间"的预备结构，作为复杂度推导的出发点：

建立一个完美哈希表，表中不仅包含动态集合中的每一个元素，还包含集合中每个元素二进制表示的每一个前缀。

以题中例子说明：设 $u = 16$，则 $\lg u = 4$。若 $x = 13$ 在集合中，因 $13$ 的二进制表示为 $1101$，完美哈希表中就需要包含字符串 $1$、$11$、$110$、$1101$ 四条前缀记录。除此之外，再维护一个按递增顺序排列的、由集合中当前元素组成的双向链表。

该结构为后续操作提供了两个关键能力：

1. 哈希表：对任意键 $x$ 的任意前缀做 $O(1)$ 的成员查询（完美哈希保证无冲突、最坏情形常数时间）；
2. 双向链表：以 $O(1)$ 时间获取当前最小、最大元素（链表头、链表尾），并能在 $O(1)$ 内从任一元素跳到其前驱/后继。

子问题 a：空间复杂度 $O(n\lg u)$

由 第 11.5 节 的结论，完美哈希表存储 $m$ 个元素需要 $O(m)$ 空间。在规模为 $u$ 的全域中，每个元素贡献 $\lg u$ 条前缀记录（二进制位数即前缀个数），因此哈希表部分需要 $O(n\lg u)$；双向链表存储 $n$ 个元素需要 $O(n)$。合计：

$$O(n\lg u) + O(n) = O(n\lg u).$$

答案的关键在于："前缀"是比"元素"多一个 $\lg u$ 因子的信息量——每个 $n$ 元素的二进制串被拆成 $\lg u$ 个前缀存进哈希表，这是初步结构空间超线性（相对 $n$）的根源，也正是后续聚类优化的切入点。

子问题 b：各操作的实现与复杂度

题目要求把 MINIMUM/MAXIMUM 做到 $O(1)$，把 MEMBER、PREDECESSOR、SUCCESSOR 做到 $O(\lg\lg u)$，把 INSERT、DELETE 做到 $O(\lg u)$。题解给出的实现思路如下：

• MINIMUM / MAXIMUM（$O(1)$）：直接查看关联双向链表的首元素与末元素，链表头即最小、链表尾即最大。
• MEMBER（$O(1)$）：实际上可以做到 $O(1)$——因为只是对完美哈希表做一次成员查询，完美哈希保证单次查找为常数时间。
• PREDECESSOR / SUCCESSOR（$O(\lg\lg u)$）：这是最精妙的部分。假定存在一棵保存了所有元素及其前缀的二叉树；对哈希表查询某个元素时，若该元素在树中则返回指向其在二叉搜索树中位置的指针，否则返回 $\text{NIL}$；每个叶子节点带有指向其在双向链表中位置的指针。设 $x$ 为要寻找后继的那个数：
  1. 先在哈希表中对 $x$ 的前缀做二分查找，找出与 $x$ 某个前缀匹配的最长哈希前缀 $y$。因为每次检查某个前缀是否在哈希表中只需 $O(1)$，而 $x$ 共有 $\lg u$ 个前缀，二分查找代价为 $O(\lg\lg u)$。
  2. 关键观察：$y$ 在二叉搜索树中至多只有一个孩子——若它同时有左右两个孩子，则其中一个孩子必然与 $x$ 共享更长的前缀，与"$y$ 是最长匹配前缀"矛盾。
  3. 于是可以"补全"缺失的孩子指针：左孩子缺失时，让左孩子指针指向二叉搜索树中小于 $y$ 的最大标号叶子；右孩子缺失时，让右孩子指针指向 $y$ 的后继。
  4. 若 $y$ 是叶子节点，则 $y = x$，直接沿指针跳到 $x$ 在双向链表中的位置（$O(1)$），其后继就是链表中的下一个元素；若 $y$ 不是叶子节点，则按需沿其前驱或后继指针访问。两种路径都能以 $O(1)$ 定位到正确元素，因此总运行时间 $O(\lg\lg u)$。
• INSERT / DELETE（$O(\lg u)$）：必须为元素的每一个二进制位向哈希表插入/删除一条前缀记录，并更新相应指针，共 $\lg u$ 条记录，故为 $O(\lg u)$。

这部分解答与 docs/Chap12/12.2.md 中二叉搜索树的 TREE-MINIMUM、TREE-MAXIMUM、TREE-PREDECESSOR 等查询例程天然衔接——哈希表给出的"指针"定位到树中节点后，前驱/后继的获取正是这些经典 BST 操作的直接复用。

---

3. 空间优化：把 $O(n\lg u)$ 压到 $O(n)$

初步结构虽然查询极快，但空间 $O(n\lg u)$ 在 $u$ 很大时不可接受。题目给出三处结构性改动：

1. 聚类（clustering）：把 $n$ 个元素聚成 $n / \lg u$ 组，每组大小为 $\lg u$（先假定 $\lg u$ 整除 $n$）。第一组是集合中最小的 $\lg u$ 个元素，第二组是次小的 $\lg u$ 个元素，依此类推——按值的大小切分全域，而不是按位切分，这是与 vEB 树递归切分思路的本质区别。
2. 代表（representative）：为每组指定一个"代表"值。第 $i$ 组的代表不小于第 $i$ 组的最大元素，且小于第 $(i+1)$ 组的每个元素；最后一组的代表可以取最大可能元素 $u - 1$。注意：代表可以是不在集合中的值，它只是一个"分隔符"性质的哨兵。
3. 组内红黑树：每组 $\lg u$ 个元素存放在一棵平衡二叉搜索树（例如红黑树）中。每个代表指向其所在组的红黑树，每棵红黑树也回指本组的代表。

最终，完美哈希表只存储各组代表，而这些代表同时保存在一条按递增顺序排列的双向链表中。这一结构即题目定义的 y-fast trie。

这里有个值得注意的类比：y-fast trie 用"代表链表"扮演了 vEB 树中 summary 的角色，用"组内红黑树"扮演了 cluster 的角色。对比 问题 20-1 中 RS-vEB 树把 cluster 数组换成动态哈希表、且只存非空聚类的做法，两者殊途同归：都只对"非空的部分"付出空间代价，从而摆脱对 $u$ 的线性依赖。

---

4. y-fast trie 的六大操作与全部子问题解答

子问题 c：空间复杂度 $O(n)$

双向链表含有的元素少于 $n$ 个（确切说只有 $n / \lg u$ 个代表），而所有红黑树合计含 $n$ 个节点，因此：

• 红黑树部分：$O(n)$；
• 代表双向链表：$O(n / \lg u) = O(n)$；
• 完美哈希表：只存 $n / \lg u$ 个代表，由 11.5 节结论为 $O(n / \lg u) = O(n)$。

总空间 $O(n)$。对比子问题 a 的 $O(n\lg u)$，空间缩减正是通过"每个元素只以其组内红黑树节点的形式存一份，而前缀信息只保留在数量为 $n/\lg u$ 的代表上"实现的。

子问题 d：MINIMUM / MAXIMUM（$O(\lg\lg u)$）

• MINIMUM：先在双向链表中以 $\Theta(1)$ 找到最小代表，然后在该代表的红黑树中找最小元素——红黑树高度为 $O(\lg\lg u)$（树中至多 $\lg u$ 个节点），故 TREE-MINIMUM 耗时 $O(\lg\lg u)$。
• MAXIMUM：对称地，找最大代表后取该组红黑树的最大元素，同为 $O(\lg\lg u)$。

注意此处与初步结构（$O(1)$）的差别：y-fast trie 放弃了常数时间的 MINIMUM/MAXIMUM，换来空间从 $O(n\lg u)$ 降到 $O(n)$——这是本题的核心权衡。

子问题 e：MEMBER（$O(\lg\lg u)$）

流程分两步：

1. 在代表链表中用二分查找找到大于 $k$ 的最小代表，耗时 $\Theta(\lg\lg u)$（代表总数为 $n/\lg u$，对其做二分查找恰为 $\lg(n/\lg u) \le \lg\lg u$ 量级）；
2. 在该代表对应的红黑树中查找 $k$，红黑树高度 $\lg u$，查询 $O(\lg\lg u)$。

两步合计 $O(\lg\lg u)$。若 $k$ 落在某组的取值区间内，则必然能在该组树中找到或确认不存在。

子问题 f：PREDECESSOR / SUCCESSOR（$O(\lg\lg u)$）

如果能找到大于等于 $x$ 的最小代表，就能确定包含 $x$ 前驱或后继的那棵红黑树。实现方式：

• 先对 $x$ 调用 PREDECESSOR 或 SUCCESSOR 例程以定位正确的树，定位过程 $O(\lg\lg u)$；
• 由于每组红黑树高度为 $\lg u$，在树内查找前驱/后继为 $O(\lg\lg u)$。

前后相加仍是 $O(\lg\lg u)$。这一步实质是"先在代表层二分（$\lg(n/\lg u)$ 层），再在树内下潜（$\lg\lg u$ 层）"的两段式搜索，与 MEMBER 的路径结构一致。

子问题 g：INSERT / DELETE 的下界 $\Omega(\lg\lg u)$

与子问题 e 同理：插入/删除必须先以 $\Theta(\lg\lg u)$ 在代表链表中定位所属聚类（找到 $x$ 应落入哪一组），再在组内红黑树上执行 $O(\lg\lg u)$ 的插入/删除与结构调整。因此任何实现都至少付出 $\Omega(\lg\lg u)$ 的时间——该下界由"定位聚类"这一不可避免的二分查找步骤决定。

子问题 h：把 INSERT / DELETE 摊还到 $O(\lg\lg u)$

前文假定每组恰好 $\lg u$ 个元素，这要求每组满员才能维持树高 $O(\lg\lg u)$，插入/删除一旦导致组大小失衡就需要重建整棵树。题解通过放松组大小的限制来摊还：

只要求每组至少 $\frac{1}{2}\lg u$ 个元素、至多 $2\lg u$ 个元素。

在此区间内，红黑树高度始终是 $O(\lg\lg u)$，所有查询操作的渐近时间不受影响。对越界的组执行如下维护策略：

• 红黑树太大：在中位数处对半分裂成两棵；
• 红黑树太小：与相邻的一棵树合并；
• 合并后若又过大：在中位数处再分裂；
• 树发生分裂：创建新代表（并把它插入代表链表与哈希表）；
• 两棵树合并：删除被合并掉的那个代表。

单次分裂/合并的代价：需要在存放代表的哈希表/链表中插入或删除一个元素，由子问题 b 知为 $O(\lg u)$。

摊还论证（题解的核心）：

• 一棵红黑树的规模从 $\lg u$ 增长到 $2\lg u$ 至少需要 $\lg u$ 次插入，才会触发一次分裂；
• 一棵红黑树的规模从 $\lg u$ 缩减到 $\frac{1}{2}\lg u$ 至少需要 $\frac{1}{2}\lg u$ 次删除，才会触发一次合并。

因此，每次插入或删除所摊还的合并、分裂及代表更新的开销为 $O(1)$（把 $O(\lg u)$ 的一次性代价除以 $\Theta(\lg u)$ 次触发它的操作）。再加上定位聚类的 $\Theta(\lg\lg u)$ 与组内红黑树操作的 $O(\lg\lg u)$，INSERT/DELETE 的摊还成本为：

$$O(\lg\lg u).$$

这正是题目所要求的最终结论。这套"阈值区间 + 按中位数分裂/与邻居合并"的思路，与 第 17.4 节动态表 的扩张/收缩策略（负载因子低于 $1/4$ 收缩、高于 $1/2$ 扩张）在摊还分析的方法论上完全同构：都通过"只在工作量累积到阈值时才做昂贵重构"来平摊成本。

---

5. 仓库佐证：y-fast trie 依赖的完整知识链

y-fast trie 并非孤立结构，它显式依赖本书前几章的多个前置结果，这些内容在当前仓库中均有对应题解可供对照：

依赖的知识点	在 y-fast trie 中的角色	仓库对应文档
完美哈希	代表（及初步结构中的前缀）的 $O(1)$ 无冲突查询，支撑所有 $O(\lg\lg u)$ 定位步骤	docs/Chap11/11.5.md
双向链表	代表按序串联，支撑 MINIMUM/MAXIMUM 与代表二分	docs/Chap10/10.2.md
二叉搜索树查询	TREE-MINIMUM / TREE-MAXIMUM / TREE-PREDECESSOR / TREE-SUCCESSOR 例程，用于组内操作	docs/Chap12/12.2.md
红黑树	组内平衡结构，保证树高 $O(\lg\lg u)$ 与 $O(\lg\lg u)$ 的动态操作	docs/Chap13/13.1.md、docs/Chap13/13.3.md、docs/Chap13/13.4.md
动态表与摊还分析	子问题 h 中"分裂/合并 + 摊还 $O(1)$"的论证模板	docs/Chap17/17.4.md、docs/Chap17/17.1.md
精简空间 vEB 树	同一章的对照方案：以动态哈希表替代 cluster 数组，实现 $O(n)$ 空间	docs/Chap20/Problems/20-1.md

其中两个对照关系尤其值得深读：

• 与问题 20-1 的空间策略对比：RS-vEB 树把空间从 $O(u)$ 降到 $O(n)$ 靠的是"动态表只存非空聚类"，y-fast trie 把空间从 $O(n\lg u)$ 降到 $O(n)$ 靠的是"只为代表建哈希表"。两题共同回答了"如何让高级数据结构的内存随实际数据量而非全域规模增长"这一工程核心问题。
• 与红黑树动态化的关系：问题 17-2 "Making binary search dynamic" 展示了用 $\lg n$ 棵满二叉搜索树构造动态集合并摊还复制的技巧，与子问题 h 的"分裂/合并 + 摊还"异曲同工，可相互印证摊还论证的写法。

---

6. 总结：y-fast trie 的设计要点速览

关注点	结论
目标性能	查询类操作最坏情形 $O(\lg\lg u)$；INSERT/DELETE 摊还 $O(\lg\lg u)$
空间	$O(n)$（子问题 c）
初步结构空间	$O(n\lg u)$，因每个元素贡献 $\lg u$ 条前缀记录（子问题 a）
核心改动	聚类（每组 $\lg u$ 个元素）→ 代表（哨兵值）→ 组内红黑树 → 只哈希代表
查询路径	代表链表二分（$\lg\lg u$ 量级）→ 组内红黑树下潜（$\lg\lg u$）
动态维护	组大小限制在 $[\frac{1}{2}\lg u,\ 2\lg u]$，越界则分裂/合并，摊还 $O(1)$
前置知识	完美哈希（11.5）、双向链表（10.2）、BST 查询（12.2）、红黑树（13）、摊还分析（17）

y-fast trie 的价值在于：它以"放弃常数时间 MINIMUM/MAXIMUM"为代价，换来与精简 vEB 树相同级别的 $O(n)$ 空间，同时保住全部查询操作的 $O(\lg\lg u)$ 最坏情形界。理解它的两段式搜索路径与"阈值 + 分裂合并"的摊还维护，等于同时掌握了哈希、平衡树与摊还分析三大工具在单一数据结构中的协同——这也是它至今仍是高级数据结构课程与面试中"空间高效动态集合"经典考题的原因。