CLRS 第 20 章习题 20-1：van Emde Boas 树的空间复杂度分析与 RS-vEB 树改进

本篇基于 CLRS 仓库中的 Problem 20-1，完整解析 van Emde Boas（vEB）树的空间需求递推式 $P(u) = (\sqrt u + 1)P(\sqrt u) + \Theta(\sqrt u)$ 及其 $O(u)$ 解法，并给出"减空间 van Emde Boas 树"（RS-vEB tree）的结构定义、建树伪代码、INSERT 与 SUCCESSOR 操作的修改版伪代码，以及期望时间 $O(\lg\lg u)$ 与空间的完整论证。读完后你将掌握：如何用动态哈希表把 vEB 树的空间从依赖宇宙大小 $u$ 改造为依赖实际元素个数，并理解该结构为何能以 $O(1)$ 时间创建。

一、问题背景：vEB 树的空间瓶颈

vEB 树（van Emde Boas tree）是处理大小为 $u$ 的整数宇宙上的动态集合的经典结构，支持 $\text{MEMBER}$、$\text{INSERT}$、$\text{DELETE}$、$\text{MINIMUM}$、$\text{MAXIMUM}$、$\text{SUCCESSOR}$、$\text{PREDECESSOR}$ 等操作，时间均为 $O(\lg\lg u)$ 或更优。其递归结构是：一个宇宙大小为 $u$ 的 vEB 树 $V$ 包含

• 一个"概要树"（summary tree）：宇宙大小为 $\sqrt{\uparrow}u$ 的 vEB 树，记录哪些簇非空；
• 一个"簇数组"（cluster array）：$\sqrt{\uparrow}u$ 个宇宙大小为 $\sqrt{\downarrow}u$ 的 vEB 树；
• 标量属性 $V.min$、$V.max$ 和宇宙大小 $V.u$。

本习题（对应教材第 20.3 节的习题 20-1）研究两个问题：

1. 标准 vEB 树的空间开销有多大？ 递推式为

$$P(u) = (\sqrt u + 1) P(\sqrt u) + \Theta(\sqrt u). \tag{20.5}$$

2. 如何把空间从"依赖宇宙大小 $u$"改为"依赖实际存储的元素个数 $n$"? 答案是引入 RS-vEB 树（reduced-space van Emde Boas tree，减空间 vEB 树）。

一个重要的动机来自仓库内 20.3-6 的习题：创建一个宇宙大小为 $u$ 的 vEB 树需要 $O(u)$ 时间，若要摊还地让每个操作都做到 $O(\lg\lg u)$，至少需要 $n \ge u / \lg\lg u$ 次操作。也就是说，标准 vEB 树"大而空"的成本必须由足够多的实际操作来平摊。RS-vEB 树正是从结构层面消除这一空耗：空间与时间都只与实际存入的元素相关。为简化讨论，与原文档一致，假设 $\sqrt u$ 恒为整数（即 $u$ 是 4 的幂）。

二、标准 vEB 树的空间递推式 (20.5) 从何而来

2.1 逐项分解空间构成

一个宇宙大小为 $u$ 的 vEB 树需要存储：

组成部分	数量/规模	空间贡献
概要树 summary	1 棵宇宙大小为 $\sqrt u$ 的 vEB 树	$P(\sqrt u)$
簇数组 cluster	$\sqrt u$ 棵宇宙大小为 $\sqrt u$ 的 vEB 树	$\sqrt u \cdot P(\sqrt u)$
标量 $V.u$、$V.min$、$V.max$	3 个 $O(u)$ 量级的数	每个 $\Theta(\lg u)$，合计 $\Theta(\lg u)$
簇数组的 $\sqrt u$ 个指针	$\sqrt u$ 个指针	$\Theta(\sqrt u)$

最后两项中，$\Theta(\lg u)$ 与 $\Theta(\sqrt u)$ 合并为一个 $\Theta(\sqrt u)$，得到

$$P(u) = P(\sqrt{\uparrow}u) + \sqrt{\uparrow}u \cdot P(\sqrt{\downarrow}u) + \Theta(\sqrt u).$$

由于题目假设 $\sqrt u$ 是整数，可令 $u = 2^{2m}$，于是 $\sqrt u = 2^m$，且 $\sqrt{\uparrow}u = \sqrt{\downarrow}u = \sqrt u$，上式恰好化为

$$P(u) = (1 + 2^m)P(2^m) + \Theta(\sqrt u) = (\sqrt u + 1) P(\sqrt u) + \Theta(\sqrt u),$$

即式 (20.5)。

2.2 证明 $P(u) = O(u)$

关键事实：对 $u$ 连续开平方，最多 $\lg\lg u$ 次就会降到 2（这正是 vEB 树递归深度的来源，与 Problem 3-6.e 中迭代函数次数的结论一致）。直接把递推式展开 $\lg\lg u$ 层：

$$P(u) \le \Big(\prod_{i = 1}^{\lg\lg u} (u^{1 / 2^i} + 1) \Big) P(2) + \sum_{i = 1}^{\lg\lg u} \Theta(u^{1 / 2^i}) (u^{1 / 2^i} + 1).$$

分两部分估计：

• 乘积项：取每个二项式的最大项，$u$ 的总指数为 $\sum_{i=1}^{\lg\lg u} 2^{-i} < 1$，这是公比为 $1/2$ 的几何级数部分和。因此乘积项是 $o(u)$。
• 求和项：第 $i$ 项的量级是 $u^{2 / 2^i}$。当 $i = 1$ 时恰为 $O(u)$；当 $i > 1$ 时 $2 / 2^i < 1$，对应项为 $o(u)$。

全部项中最大者是 $O(u)$，故 $P(u) = O(u)$。

这解释了为什么"标准"vEB 树的空间是 $\Theta(u)$ 量级：即使树里只存了极少数元素，簇数组的 $\sqrt u$ 个指针和概要树仍然按宇宙大小全额存在。

三、RS-vEB 树的三大结构改动

为了把空间需求从 $u$ 改为取决于实际元素数 $n$，把 vEB 树 $V$ 做如下三处修改（原文档定义）：

1. V.cluster 由定长指针数组改为动态哈希表：哈希表以簇编号 $i$ 为键，存储指向宇宙大小为 $\sqrt u$ 的 RS-vEB 树的指针；查找第 $i$ 个簇只需对键 $i$ 做一次哈希搜索。该哈希表用第 17.4 节的动态表（dynamic table）实现，其空间与"非空簇的个数"成正比，而非与 $\sqrt u$ 成正比。动态表的摊还分析可参考仓库内 Chap17/17.4 各题（如用势函数 $\Phi(T) = |2 \cdot T.num - T.size|$ 证明动态插入/删除摊还 $O(1)$）。
2. 哈希表只存非空簇的指针：查找一个空簇返回 $\text{NIL}$，表示该簇为空——空簇根本不需要分配子树。
3. V.summary 可为 $\text{NIL}$：当所有簇都为空时 $V.summary = \text{NIL}$；否则指向一棵宇宙大小为 $\sqrt u$ 的 RS-vEB 概要树。

由此产生"惰性创建"语义：子树与概要树都在第一次真正需要时才分配。当需要向一棵空的 RS-vEB 树插入元素时，用下面的过程建树（原文档给出的伪代码）：

CREATE-NEW-RS-vEB-TREE(u)
    allocate a new vEB tree V
    V.u = u
    V.min = NIL
    V.max = NIL
    V.summary = NIL
    create V.cluster as an empty dynamic hash table
    return V

对照仓库中 20.2-6 的 MAKE-PROTO-vEB(u) 可以看到差异的本质：标准建树过程对 V.cluster[0..sqrt(u)-1] 逐一递归建子树、并递归建概要树，总耗时 $O(u)$；而 CREATE-NEW-RS-vEB-TREE 只分配一个节点和一张空动态表，任何与 $u$ 成比例的分配都被推迟了。

四、修改后的 RS-VEB-TREE-INSERT

原解答的要点是："沿用普通 vEB 树的 VEB-TREE-INSERT，在每次访问 cluster 或 summary 之前先检查其是否已初始化，若未初始化则就地创建。"下面据此给出可独立阅读的完整伪代码。

先给出两个辅助过程：

RS-VEB-CLUSTER-INSERT(V, i, x)
    # 取第 i 个簇；若不存在则惰性创建，返回 (cluster, justCreated)
    if V.cluster[i] == NIL
        V.cluster[i] = CREATE-NEW-RS-vEB-TREE(sqrt(u))
        if V.summary == NIL
            V.summary = CREATE-NEW-RS-vEB-TREE(sqrt(u))
        RS-VEB-TREE-INSERT(V.summary, i)      # 把簇 i 标记为非空
        return (V.cluster[i], true)
    return (V.cluster[i], false)

主过程：

RS-VEB-TREE-INSERT(V, x)
    if V.min == NIL                    # 空树
        V.min = x
        V.max = x
    else
        if x < V.min
            V.min = x
        else
            (C, justCreated) = RS-VEB-CLUSTER-INSERT(V, high(x), low(x))
            if C.min == NIL
                C.min = x
                C.max = x
            else
                RS-VEB-TREE-INSERT(C, low(x))
                V.max = max(V.max, x)

要点说明：

• high(x) / low(x) 与第 20.3 节定义一致，把 $x$ 拆为簇编号与簇内偏移（要求 $\sqrt u$ 为整数，恰好保证 $\lfloor \lg \sqrt u \rfloor = \lceil \lg \sqrt u \rceil$，拆分无歧义）。
• 惰性创建的触发点只在两处：首次写入某个空簇、以及首次让 summary 从 $\text{NIL}$ 变为概要树。每次触发调用 CREATE-NEW-RS-vEB-TREE，开销为常数（见第六节）。
• 当整个树为空时（$V.min = \text{NIL}$），直接设置 $min/max$ 并返回，不创建任何子结构——这正是空间只随 $n$ 增长的关键。
• 与 20.3-4 讨论的问题呼应：若 $x$ 已在集合中，标准 vEB 树的 INSERT 可能在基子树中重复插入；RS-vEB 树同样需要在入口先检查成员资格（用成员标记或沿结构下探验证），本文伪代码默认按集合语义插入互异键。

五、修改后的 RS-VEB-TREE-SUCCESSOR

原解答的要点是："推迟到即将使用 cluster[i] 或 summary 的时刻，再按需分配。"完整伪代码如下：

RS-VEB-TREE-SUCCESSOR(V, x)
    if V.max != NIL and x == V.max
        return NIL
    if V.min == NIL              # 空树，x 必无后继
        return NIL
    (C, justCreated) = RS-VEB-CLUSTER-INSERT(V, high(x), low(x))
    y = RS-VEB-TREE-SUCCESSOR(C, low(x))
    if y != NIL
        return high(x) * sqrt(u) + y
    # 本簇内（或本簇未覆盖到）没有后继，查概要树找下一个非空簇
    if V.summary == NIL
        return NIL
    i = RS-VEB-TREE-SUCCESSOR(V.summary, high(x))
    if i == NIL
        return NIL
    C2 = V.cluster[i]
    return i * sqrt(u) + C2.min

要点说明：

• 若 $x$ 是 $V.max$，直接返回 $\text{NIL}$，不需要任何子结构。
• 第一优先级在本簇内找 $low(x)$ 的后继；簇不存在时由辅助过程惰性创建（新簇必为空，递归自然返回 $\text{NIL}$，随后转查概要树）。
• 第二优先级查概要树中 high(x) 的后继簇 $i$，答案就是该簇的最小元素 $i \cdot \sqrt u + C2.min$。概要树为 $\text{NIL}$ 说明没有其他非空簇，返回 $\text{NIL}$。
• 与 INSERT 不同，SUCCESSOR 在"本簇为空且概要树也为 $\text{NIL}$"的分支上会临时创建空簇，但不创建概要树，创建成本仍为常数。

六、期望时间 $O(\lg\lg u)$ 与空间分析

6.1 时间：为什么惰性创建不破坏 $O(\lg\lg u)$

在简单一致哈希（simple uniform hashing）假设下（该假设与 Chap11/11.2 各题使用的假设相同），动态哈希表的单次查/插期望 $O(1)$。对比标准 VEB-TREE-INSERT 与 VEB-TREE-SUCCESSOR，新过程引入的额外操作只有：

• 对 V.cluster 的一次键查找（期望 $O(1)$）；
• 至多一次 CREATE-NEW-RS-vEB-TREE（常数时间，见下文）；
• 至多一次向 summary 的插入（期望 $O(1)$ 加上一棵 $\sqrt u$ 宇宙的递归插入，但注意它发生在递归路径的同一层，已被该层的 $O(\lg\lg u)$ 预算覆盖）。

递归结构本身没有改变：递归深度仍是 $\lg\lg u$（对 $u$ 连续开方直到 2），每层新增的只是常数期望开销。因此 RS-VEB-TREE-INSERT 与 RS-VEB-TREE-SUCCESSOR 的期望时间都是 $O(\lg\lg u)$。（注：原文档答案此处写作 $O(\lg\lg n)$，属笔误，应为 $O(\lg\lg u)$。）

6.2 空间：errata 修正为 $O(n \lg n)$

题目 (f) 原文要求证明"假设永不删除元素时，RS-vEB 树空间为 $O(n)$"。但仓库解答明确指出：根据教材 errata，此问应改为证明空间是 $O(n \lg n)$。论证思路如下（转述自仓库解答）：

• 插入一个元素时，可能要向某张动态哈希表加一个条目：动态表按摊还分析每次插入摊还常数空间，即常数级别的额外开销；
• 若这次插入同时使某个簇从空变非空，还要向概要树插入一个元素，且对应簇条目是一棵常规模块大小的 RS-vEB 树（空动态表 + 3 个标量）。可以把"概要表这次新增条目"的费用，**分摊（amortize/charge）**到本次在簇表中新增的那个"新最小元素条目"上——因为每次插入至少会在某处产生一个最小元素条目，分摊后每个新条目的存储成本仍是常数；
• 但元素要"穿透"的哈希层级数为 $\lg\lg u$，且每层的概要树/簇表中都可能留下至多 $\lg u$ 量级的足迹，逐层累加后总量为 $O(n \lg n)$，而不是严格的 $O(n)$——这就是 errata 把目标从 $O(n)$ 放宽到 $O(n\lg n)$ 的原因。

即便按 $O(n\lg n)$ 计算，相比标准 vEB 树的 $\Theta(u)$ 也是数量级的改进：当 $n \ll u$ 时（例如 $u = 2^{64}$、$n$ 只有几万），标准结构要付出与 $u$ 成正比的固定空间，而 RS-vEB 树只与实际元素相关。

6.3 创建空树的时间：$O(1)$ 对比 $O(u)$

题目 (g)：创建一棵空 RS-vEB 树要多久？答案是常数时间 $O(1)$。直接看 CREATE-NEW-RS-vEB-TREE(u) 即可：唯一与 $u$ 相关的步骤是第 2 行初始化标量 $V.u = u$，这是常数时间；其余语句（置空 $min$、$max$、$summary$，创建一张空动态表）都与 $u$ 无关。对照 20.2-6 中 MAKE-PROTO-vEB 需要递归创建 $\sqrt u$ 棵子树与概要树（耗时 $\Theta(u)$），以及 20.3-6 中"建树 $O(u)$ 时间需要 $n \ge u / \lg\lg u$ 次操作来摊还"的结论，RS-vEB 树把这笔 $O(u)$ 的建树成本彻底消灭了。

七、小结：RS-vEB 树带来的三项收益

把本文与仓库内相关习题放在一起，可以得到一个完整的对照：

指标	标准 vEB 树	RS-vEB 树
建树时间	$O(u)$（见 20.2-6、20.3-6）	$O(1)$
空间	$\Theta(u)$（式 (20.5) 的解）	$O(n \lg n)$（errata 修正口径）
INSERT / SUCCESSOR	最坏 $O(\lg\lg u)$	期望 $O(\lg\lg u)$（简单一致哈希下）
摊还前提	需 $n \ge u / \lg\lg u$ 次操作平摊建树成本	无建树成本可平摊

RS-vEB 树的本质设计是"惰性 + 动态表"：簇数组换成只存非空键的动态哈希表，概要树在所有簇为空时置 $\text{NIL}$，任何子结构都在第一次被访问时才创建。这一思想在 Problem 20-2（$y$-fast trie）中进一步演化——那里用完美哈希表加每组 $\lg u$ 个元素的平衡树分组，在 $O(n)$ 空间内同样做到 $O(\lg\lg u)$ 的最坏/摊还操作时间，可以视为本题思路的延续。

参考文档（仓库内相对路径）：

• 本文主体：Problem 20-1
• vEB 树背景与相关习题：20.3 节习题、20.2 节习题、20.1 节习题
• 动态哈希表的摊还分析背景：17.4 节习题
• 简单一致哈希假设背景：11.2 节习题