van Emde Boas 树 | Codeboy's Blog

形式陈述

宇宙、成员与表示不变量

van Emde Boas 树维护有限整数集合，并提供Word-RAM 前驱接口。先把整数宇宙上界补到 $U=2^w$ ，其中 $w\ge1$ ；这至多把原宇宙扩大不到两倍，填充位置不作为合法输入。令

\ell=\lfloor w/2\rfloor,\qquad u=\lceil w/2\rceil,

则键可分成高、低两段：

\operatorname{high}(x)=\lfloor x/2^\ell\rfloor,\quad \operatorname{low}(x)=x\bmod2^\ell,\quad \operatorname{index}(a,b)=a2^\ell+b.

每个非基例节点保存 min、max 和 $2^u$ 个宇宙为 $2^\ell$ 的 cluster，另有宇宙为 $2^u$ 的 summary。空节点用空标记表示。当前最小键只存在本节点的 min 字段中，不重复存入 cluster；其余键的低段存在对应 cluster。Summary 恰好记录非空 cluster 的编号。Max 是最大键的缓存值，集合多于一项时，它对应的键仍在 cluster 中。

$U=2$ 时直接处理两种可能成员，不再分簇。本文的最坏操作界使用预先分配的基本版本：建立全部递归结构的时间、空间为 $\Theta(U)$ ；此后字级拆分、数组访问和 min/max 更新按常数成本计算。

查询与更新怎样只走一条递归链

先说明严格前驱，即小于 $x$ 的最大成员。空节点或 $x\le min$ 时无解， $x>max$ 时直接返回 max。其余情况下，若所属 cluster 的 min 小于 low $(x)$ ，就在该 cluster 内递归找严格前驱；否则在 summary 中递归找严格小于 high $(x)$ 的非空簇编号，再读取该簇的 max。Summary 中无更小簇时，返回另存的全局 min。

所链接问题页采用非严格前驱 $y\le x$ 。可先作成员查询：若 $x$ 存在就直接返回它，否则调用上面的严格过程。两次对数级查询仍保持相同渐近界。严格后继对称，但需先处理 $x<min$ 时直接返回 min 的分支。

插入先处理重复键；新键进入空节点时，只设置 min/max。若它小于当前 min，就交换两者，让旧 min 进入簇。目标 cluster 原为空时，设置它的 min/max 是常数工作，唯一递归发生在向 summary 插入簇编号；目标簇非空时，只递归更新该簇，summary 不变。

删除先确认键存在。单元素节点直接清空；删除 min 时，从第一个非空簇取最小键提升为新 min，再从该簇删除它。若簇因此为空，清簇本身为常数工作，只递归删除 summary 中的编号；否则只递归更新簇。最后根据剩余簇或 min 修正 max。

直觉

高位决定大区间，低位决定区间内位置。每层把字长约减半，因此只需对数于字长的递归深度。Min/max 提供的常数时间判断让算法先决定应进入当前簇还是 summary，而不是两条支路都递归搜索。

把最小键单独保存也承担实际作用：给空簇放入第一项时不用继续向下创建成员，所以簇由空变非空时，可以把唯一昂贵递归留给 summary。这正是插入仍走一条递归链的原因。

例子与边界

十六元宇宙的完整状态

$U=16$ 时，高低各两位。集合 $\{2,3,12\}$ 的根保存 min $=2$ 、max $=12$ ；cluster 0 中只存低位 $\{3\}$ ，cluster 3 中存 $\{0\}$ ，其他簇为空，summary 为 $\{0,3\}$ 。

查询 $10=(10\mid10)_2$ 的前驱时，cluster 2 为空；summary 中小于 2 的最大簇编号为0，读取 cluster 0 的 max 得3，答案为 index $(0,3)=3$ 。查询3的非严格前驱则由成员检查直接返回3；严格前驱才是另存的2。

删除2时，把 cluster 0 的最小低位3提升为根 min，再从 cluster 0 删除3。该簇变空，summary 删去0，得到 min $=3$ 、max $=12$ 、summary $=\{3\}$ 。剩下的全局最小键仍不重复存入簇。

字长与空间边界

若只为了每层恰好开平方而把字长再补到二次幂，原整数宇宙可能被放大到近乎平方，空间会随之膨胀。上面的高低段允许相差一位，所以只需先把宇宙补到普通二次幂。

预分配的 $\Theta(U)$ 空间在 $U\gg n$ 时可能很大。改成按需分配、哈希簇或其他压缩版本，必须重新说明分配和查询成本；x-fast/y-fast Trie提供另一种以空间和随机性换取整数查询效率的路线。

van Emde Boas 布局则递归摆放一棵既有树的节点，以改善缓存局部性。它与本页的整数集合查询结构共享名称，但递归对象和接口不同。

推论与应用

单支递归与总界

用递推关系计量字长 $w$ ，核心查询或已确认合法的更新满足

T(w)\le T(\lceil w/2\rceil)+O(1), \qquad T(1)=O(1),

因此操作为最坏 $O(1+\log w)=O(1+\log\log U)$ 。前置的成员检查至多再走一条同样长度的链。判断目标簇是否含候选只读 min/max；若先递归失败后再递归 summary，就失去了上述单支递推依据。

在高低段恰好等长的层，预分配空间可写成

S(U)=(\sqrt U+1)S(\sqrt U)+O(\sqrt U).

末项计入簇指针数组，递归解为 $\Theta(U)$ ；奇数字长使用大小不同的高低段，结论仍成立。所有这些费用按补齐后的宇宙计，而非仅按已存键数计。

当 $U=n^{O(1)}$ 时，查询界可进一步写为 $O(1+\log\log n)$ ；没有这条参数关系，就保留 $U$ 或 $w$ 。动态坐标压缩还要维护新键的排名与旧编号，不能把改变宇宙的工作忽略后直接代入原结构。

参考资料

Peter van Emde Boas、Robert Kaas、Erik Zijlstra，Design and Implementation of an Efficient Priority Queue，Mathematical Systems Theory 10, 1977，pp. 99–127。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，Introduction to Algorithms, 3rd ed., MIT Press, 2009，Chapter 20：min 单独存储、簇与 summary，以及各更新分支。

形式陈述 ​

宇宙、成员与表示不变量 ​

查询与更新怎样只走一条递归链 ​

十六元宇宙的完整状态 ​

字长与空间边界 ​