van Emde Boas 树

以下将 vEB 树作为 van Emde Boas 树的简称。

vEB 树存在的意义是突破 O(lgn) 操作性能的极限。在基于比较的动态集合数据结构中，是存在这样的极限的。如同基于比较的排序方法也有 O(nlgn) 的性能极限一样。

vEB 树只在有限大小的全域 u 中有效，采用位图思想。

提前说一个结论，完全体的 vEB 树所有操作都可以在 O(lglgu) 时间内完成，其中 u 是树的全域。

基本方法

这一节讲了几种基本方法，是 vEB 树的思想基础，大概发明 vEB 树的过程就是这些思想不断完善的过程。

直接寻址就是简单的位图方法。

叠加的二叉树结构是在位图上叠加一个“逻辑或”的二叉树，即树中结点的值等于两个孩子结点值的“逻辑或”。

叠加的一颗高度恒定的树在二叉树的基础改进，从底部到顶部不再是二叉树的每次结点规模缩小一半，而是每次结点规模缩小全域 u 的平方根，这样树的高度总是 2.

这三种方法是步步改进的，每次改进总会在某些方面性能有所提升。

递归结构

这一节讲的是 vEB 树的原型结构，大概是 vEB 树发展过程中的一个重要结点（至少这时候有 vEB 这个名称了）

原型的关键点是，在位图上叠加树的思想上再次改进，上层结点规模缩小为下层结点规模的平方根。改进自上一节的高度恒定的二叉树。

关于缩小规模的改进依据，是由对递归结构的性能分析方法得出的。

原型 vEB 树的结构

在具体的实现中多了一种 summary 结构，组织形式也有所变化，简单的说就是十分复杂（难以简短的用文字描述，具体的看书吧）。

原型 vEB 树的操作

这一小节分析结构上的各种操作，并分析性能

MEMBER 操作，O(lglgu)
MINIMUM 操作，O(lgu)
SUCCESSOR 操作，O(lgu lglgu)，渐进慢于 MINIMUM
INSERT 操作，O(lgu)
DELETE 操作

大部分操作都达不到 O(lglgu) 的性能，其原因是大部分操作中都进行了多次递归调用。按照递归性能的分析公式，要达到 O(lglgu) 的性能，操作中只能有一次递归。

这是标准的用公式和方法论，来指导数据结构和算法的设计，而且已经明确算法能够达到的性能。

van Emde Boas 树及其操作

这一节同样是按照结构和操作的顺序组织的。

先说改进方法，上一节中已经明确了指导思想，要减少操作中的递归为一次。但估计如何实现这一点也是前人做了许多探索，书中给出的有效改进是，在原型的基础上给每个结构增加 min 和 max 两个属性。

vEB 树结构

min 和 max 两个属性是减少递归次数的关键，书中分析了这两个属性的多种作用，能够降低多个操作的复杂性。可以说 vEB 树的性能关键就在于对 min 和 max 的巧妙利用。

其中 min 不存储在树中的任何一个簇中。

vEB 树操作

书中给出了 MINIMUM、MAXIMUM、MEMBER、SUCCESSOR、PREDECESSOR、INSERT、DELETE 等所有操作的伪代码和分析。

所有的操作最坏运行时间均为 O(lglgu)。

看到结尾我有点感慨，相比于之前的多种数据结构，vEB 树是一种在方法论和公式指导下设计出来的数据结构，让我有一种“人定胜天”的感觉。这就好比以前化学元素的发现靠的是机缘巧合和灵光一现，而现在，寻找一种新的化学元素，我们只需要按照科学的方法去尝试，就总能找到。