第 20 章 van Emde Boas 树 (van Emde Boas Trees)
核心结论
-
突破 lg n 下界：在 universe 大小 u 的整数键（无重复）场景下，vEB 树把 SEARCH/INSERT/DELETE/MINIMUM/MAXIMUM/SUCCESSOR/PREDECESSOR 都做到 O(lg lg u)。
-
排序下界回避：基于比较的排序有 (n lg n) 下界，而 vEB 树以整数键为输入——桶排序 / 计数排序同样突破；这是「特定输入 → 更快算法」的典范。
-
递归结构：每个 vEB(u) 节点存 universe 大小 u、min / max（最优元素缓存）、summary（vEB(⌈√u⌉)）和 cluster[0..⌈√u⌉−1]（每个 vEB(⌊√u⌋)）；min 不在 cluster 中。
-
结构 vs. 原型：proto-vEB 把 cluster 元素存到叶节点（每次需 2 次递归）；vEB 树加 min/max 后单次递归即可，避免 lg u 退化。
-
复杂度来源：递推 T(u) ≤ T(⌈√u⌉) + O(1) 由主定理给 T(u) = O(lg lg u)；空间 O(u) 空间、初始化 O(u)。
|
本章主旨
本章是为「整数键 + 范围 [0, u)」专门优化的优先级队列——van Emde Boas 树。它把所有动态集操作从 O(lg n)（基于比较）降到 O(lg lg u)；突破的关键是把 universe 递归地按平方根分解（u → √u → ⁴√u → …），让高度从 lg u 降到 lg lg u。章内设三节逐层演化：20.1 直接寻址与位向量（O(u) 最坏 → O(lg u) 含二叉树 → O(√u) 含度数 √u 的树）；20.2 proto-vEB 递归结构（O(lg u) MEMBER 但 MIN/SUCC 退化）；20.3 加 min/max 后达到终极的 O(lg lg u) 全部操作。本章是教科书级「为输入定制数据结构」的范例，对「比较模型下界」的突破让算法设计思维更加开阔。 |
一、核心概念
本章围绕 5 个核心概念展开：从最朴素的方法（20.1），经递归 proto-vEB（20.2），到最终的 vEB 树（20.3）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
直接寻址 / 位向量 |
A[0..u−1] 每位存 1/0；INSERT/DELETE/MEMBER O(1)；MIN/MAX/SUCCESSOR/PREDECESSOR 退化为 O(u)。 |
§20.1;粗方案揭示「需要辅助结构加速」。 |
二叉树叠加 (Binary Tree + Bit Vector) |
内部节点 = 子树 OR；MIN 向左下走、SUC 从叶子向上找「从左进且右兄弟非空」。 |
§20.1;CPU O(lg u)，但常数大；MEMBER O(lg u) 比 RB 树慢。 |
度 √u 树叠加 (Tree of constant height) |
每个内部节点汇总 √u 位；summary 数组 [0..√u−1] 表示哪些 cluster 非空；O(√u) 操作。 |
§20.1;高度恒为 2；为递归化铺路。 |
proto-vEB 递归结构 |
proto-vEB(u) = (proto-vEB(√u) summary) + (√u 个 proto-vEB(√u) cluster)；high/low/index 分键；MEMBER O(lg lg u)、MIN/SUCC O(lg u)（退化）。 |
§20.2.1;递归雏形；问题：MIN 需要两次递归（summary + cluster）。 |
vEB 树 (van Emde Boas Tree) |
在 proto-vEB 上加 min/max 缓存：MIN/MAX O(1)、SUC 通过 max 判断「必要时递归 summary」单次递归 → 全 O(lg lg u)。 |
§20.3;递推 T(u) ≤ T(⌈√u⌉) + O(1)；T(u) = O(lg lg u)。 |
二、详细笔记
2.1 预备方案
What：从最简单的方案开始——直接寻址位向量、二叉树叠加、常高度 √u 度树叠加——为递归 vEB 树铺路。
Why：直接给出 vEB 结构不易懂；通过渐进的「朴素方案」对比，可体会为何递归和 min/max 缓存能带来 O(lg lg u) 的提升。
How：
| 方案 | 操作复杂度 | 关键想法 |
|---|---|---|
位向量 A[0..u−1] |
INSERT/DELETE/MEMBER O(1)；MIN/MAX/SUC O(u) |
最简但最坏 O(u) |
位向量 + 二叉树 |
全部 O(lg u) |
内部节点 = 子树 OR，向上找第一个「右兄弟非空」的位置 |
位向量 + 度 √u 树 |
全部 O(√u) |
高恒为 2；summary 数组汇总 √u 大小 |
When：作为讲解动机——为何要「递归 + min/max」组合才能突破 lg u。
Example：u=16、集合 {2,3,4,5,7,14,15}；位向量 A = (0,0,1,1,1,1,0,1,0,0,0,0,0,1,1,0)；MIN 找到位置 2、SUC(2)=3、PRED(15)=7（向上找右侧有 1 的兄弟）。
2.2 proto-vEB 结构
What：proto-vEB(u) 递归定义为 — 基础 u=2 时存 A[0..1] 两位；u ≥ 4 时存 summary 指针 (proto-vEB(⌈√u⌉)) 与 cluster[0..⌈√u⌉−1] (proto-vEB(⌊√u⌋))；键 x 通过 high(x) = ⌊x/√u⌋ 选择 cluster，low(x) = x mod √u 作为该 cluster 的索引。
Why：递归让树高从 lg u 降到 lg lg u；但 MIN 需要「summary 找非空 cluster + cluster 找 min」两次递归，导致 T(u) = 2T(√u) + O(1) = Θ(lg u) 而非期望的 O(lg lg u)。
How：
| 操作 | 递推 |
|---|---|
复杂度 |
PROTO-VEB-MEMBER |
T(u) = T(√u) + O(1) |
O(lg lg u) ✓ |
PROTO-VEB-MINIMUM |
2 次递归（先 summary 后 cluster） |
Θ(lg u) ✗ |
PROTO-VEB-SUCCESSOR |
2 次递归 + MIN |
Θ(lg u lg lg u) ✗ |
PROTO-VEB-INSERT |
2 次递归（cluster + summary） |
Θ(lg u) ✗ |
PROTO-VEB-DELETE |
需扫描整个 cluster 重置 summary bit |
Θ(√u) ✗ |
When：作为 vEB 树的「前奏」——理解为何加 min/max 能修复递归次数过多的问题。
Example：u=16 的 proto-vEB 在 CLRS 图 20.4 中展开为 16 个 proto-vEB(2) 叶（存实际元素）+ 5 个 summary 节点。
2.3 van Emde Boas 树
What：vEB(u) = (min, max, summary → vEB(⌈√u⌉), cluster[0..⌈√u⌉−1] → vEB(⌊√u⌋))；VEB(u) 中的元素 = {V.min} ∪ ⋃ cluster[i]（但 min 不出现在任何 cluster 中）。
Why：加 min / max 让 MIN/MAX O(1)；SUC 通过 max 判断避免两次递归（若 low(x) < cluster[high(x)].max 就只递归 cluster，否则递归 summary）；DELETE 中若 cluster 变空才递归 summary 一次——总保持单次递归。
How：
| 操作 | 行为 |
|---|---|
复杂度 |
VEB-TREE-MINIMUM |
返回 V.min |
O(1) |
VEB-TREE-MAXIMUM |
返回 V.max |
O(1) |
VEB-TREE-MEMBER |
检查 V.min/V.max；否则递归 cluster[high(x)] |
O(lg lg u) |
VEB-TREE-SUCCESSOR |
base case；否则比较 high(x) 处的 max → 二选一递归 |
O(lg lg u) |
VEB-TREE-INSERT |
空 → V.MIN = V.MAX = x；否则按需 swap + 递归 cluster / summary |
O(lg lg u) |
VEB-TREE-DELETE |
多分支：min==max、NIL、x==min 等；级联向上 |
When：键是 [0, u) 整数 + 无重复 + 需要 SUCCESSOR / PREDECESSOR 时——vEB 树最优（与 Pǎtraşcu-Thorup 下界匹配）。
Example：CLRS 图 20.6 —— vEB(16) 含 {2,3,4,5,7,14,15}；min=2 (不在 cluster[0] 中)，max=15；cluster[0].min=3、cluster[3].max=15；SUC(2) = 3 直接读 min，PRE(15) = 14 通过 max 直接得，PRE(2) 返回 V.min = 2。
2.4 空间与初始化
What：vEB 树空间 O(u)（由递推 P(u) = (√u + 1)·P(√u) + Θ(√u) 解出）；初始化一棵空 vEB(u) 需 O(u) 时间。
Why：vEB 树「预分配」空间是其主要缺点——在数据稀疏时浪费大；问题 20-1 给 RS-vEB 树（reduced-space vEB）变种，用 hash 表 + 按需分配把空间降到 O(n)。
How：
| 项 | 复杂度 |
|---|---|
实现注意 |
总空间 |
P(u) = (√u+1)·P(√u) + √u → P(u) = O(u) |
总是预分配所有 summary/cluster 指针 |
初始化 |
O(u) |
调用 CREATE-NEW-vEB-TREE 全树递归创建 |
RS-vEB（问题 20-1） |
空间 O(n)，创建 O(1) |
用动态 hash 表 + 按需分配 |
y-fast tries（问题 20-2） |
空间 O(n)，操作 O(lg lg u) |
perfect hashing + RB 树每组 lg u 元素 |
When：u 与 n 数量级相当时直接用 vEB；n ≪ u 时考虑 RS-vEB / y-fast tries / 简单 hash 表。
Example：u = 2³² 时 P(u) = O(2³²) ≈ 4 GB 不可接受；RS-vEB 在 n=10⁶ 时 P(n) = O(10⁶) 可行。
2.5 vEB 树的核心数学
What：vEB 树的高效来自「平方根递归」和「min/max 缓存」两个机制的精确组合。
Why：从数学上理解 vEB 树复杂度是关键——递推 T(u) = T(√u) + O(1) 的解是 O(lg lg u) 而非线性，是 non-intuitive 的关键。
How：
| 关键递推 | 解 |
|---|---|
来源 |
MEMBER（proto-vEB / vEB） |
T(u) = T(√u) + O(1) → O(lg lg u) |
单次递归 |
MIN（proto-vEB） |
T(u) = 2T(√u) + O(1) → Θ(lg u) |
两次递归 |
平方根叠代 |
u → √u → ⁴√u → … → 2 共 lg lg u 步 |
高度 = lg lg u |
lg lg u 量级 |
对 n=2³²：lg lg 2³² = 5 步 |
子定理 S(m) ≤ S(m/2) + O(1) → S(m) = O(lg m)；回代 T(u) = O(lg m) = O(lg lg u)。
When：理解为何 vEB 操作对 u=2³² 也仅需 ~5 步——这与「lg u ≈ 32 步」的红黑树形成鲜明对比。
Example：u=2¹⁶ = 65536 → 高度 = lg lg 65536 = lg 16 = 4（只有 4 层递归）。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 20 章 vEB 树))
直接寻址
位向量Ou最坏
朴素方案
二叉树叠加
OR聚合
O(lg u)
度√u树
高恒2
O(√u)
proto-vEB
递归结构
high/low/index
MEMBER O(lg lg u)
MIN/SUC退化Θ(lg u)
vEB树
+min/max缓存
MIN/MAX O(1)
SUC单次递归
全O(lg lg u)
复杂度关键
T(u)=T(√u)+O1
S(m)=S(m/2)+O1
解O(lg lg u)
空间
P(u)=O(u)
初始化O(u)
RS-vEB变种O(n)
应用
整数键序集
比RB树快一个量级
y-fast tries
== 五、重点与易错点
. vEB 树只支持整数键 [0, u)——不支持任意 key 类型；需要先 hash 到范围再插入。
. lg lg u 通常很小（u=2³² 时仅 5）；这是 vEB 在整数键上「比 RB 树快一个量级」的来源。
. min 不出现在 cluster 中——更新 min/max 时必须特别处理「min/max 是否在 cluster 中」。
. proto-vEB 的 MIN 用两次递归退化为 Θ(lg u)；vEB 树加 min/max 后单次递归 → O(lg lg u)；这是「缓存幂等值」的典范。
. PREDECESSOR 比 SUCCESSOR 多一个特殊情形：「x 之前无 cluster 有更大键」——返回 V.min。
. DELETE 中「x == min」时需从 summary + cluster 找下一个最小值；「cluster 变空」时从 summary 删除——仍是单次递归（互斥）。
. RS-vEB 用 hash 表 + 按需分配把空间从 O(u) 降到 O(n)——但摊还复杂度变为期望 O(lg lg u)。
. vEB 树的 INSERT 在「空树」可直接 O(1) 完成（V.min = V.max = x）——这是 min/max 设计带来的副产品。
. universe 大小 u 必须是 2 的幂——非 2 幂需要 round up 到最近的 2^k，浪费空间。
. vEB 不支持重复键——重复需要额外计数（CLRS 习题 20.3-1：双倍策略 + 计数）。
. Pǎtraşcu-Thorup 下界表明 vEB 在 predecessor 操作上是最优的——即使允许随机化。
. u 较大时 vEB 树的常数量级不可忽视——初始化 O(u)、指针跳转、缓存不友好——工程中常改用 d-ary heap / B+ 树。
. vEB 树的「S(m) = S(m/2) + O(1)」与「二分查找 T(m) = T(m/2) + O(1)」形似但解不同——前者 S(m) = O(lg m)、后者 T(m) = O(lg m)——这就对了，但要注意「T(u) = 2T(√u) + O(1)」才会退化。