van Emde Boas树支持优先队列操作以及一些其他操作，每个操作最坏运行时间为O(lg lgn)，这种数据结构限制关键字必须为0~n-1的整数且无重复。

目前参数n有两个不同的用法：一个为动态集合中元素的个数，另一个为元素的可能取值范围。为避免混淆，以下用n表示集合中当前元素的个数，用u表示元素的可能取值范围，这样每个van Emde Boas树操作在O(lg lgu)时间内运行完。要存储的关键字值的全域的集合为{0,1,2，•••，u-1}，u为全域的大小。

基础方法

用一个u位的数组A[0..u-1]，存储一个值来自全域{0,1,2，•••，u-1}的动态集合。若值x属于动态集合，则元素A[x]为1；否则，A[x]为0。

叠加的二叉树结构

使用位向量上方叠加的一棵位二叉树的方法，来缩短对位向量的长扫描。位向量的全部元素组成了二叉树的叶子，并且每个内部结点为1当且仅当其子树中任一个叶结点包含1。换句话说，内部结点中存储的位就是其两个孩子的逻辑或。

使用这种树结构的操作如下：

查找集合中的最小值，从树根开始，依次指向叶结点，总是走到最左边包含1的结点。查找集合中的最大值，从树根开始，依次指向叶结点，总是走到最右边包含1的结点。查找x的后继，从x所在的叶结点开始，向上指向树根，直到从左侧进入一个结点，其右孩子结点z为1,。然后从结点z出发依次指向叶结点，始终走最左边包含1的结点。查找x的后驱，从x所在的叶结点开始，向上指向树根，直到从右侧进入一个结点，其左孩子结点z为1,。然后从结点z出发，依次指向叶结点，始终走最右边包含1的结点。插入一个值，从该叶结点到根的简单路径上每个结点都置为1。删除一个值，从该叶结点出发到根，重新计算这个简单路径上每个内部结点的位值，该值为其两个孩子的逻辑或。

叠加的一棵高度恒定的树

叠加一棵度为√u的树，来替代位向量上方叠加的二叉树。每个内部几点存储的是其子树的逻辑或，深度为1的√u个内部结点是每组√u个值的合计。定义这些结点定义一个数组summary[0…√u-1]，其中summary[i]包含1当且仅当其子数组A[i√u..((i+1)√u-1))]包含1。我们称A的这个√u位子数组为第i个簇。这种结构的操作如下：

查找最大(最小)值，在summary数组中查找最左(最右)包含1的项。查找x的后驱(前驱)，先在x的簇中向右(左)查找。如果发现1，则返回这个位置作为结构；否则，令i=x/√u，然后从下标i开始在summary数组中向右(左)查找。删除值x，设i=x/√u。将A[x]置为0，然后置summary[i]为第i个簇中所有位的逻辑或。

递归结构

现在使用结构递归，每次递归都以平方根大小缩减全域。考虑一个简单的递归式：

T(u) = T(√u) +O(１)

要设计一个递归的数据结构，该数据结构每层递归以√u为因子缩减规模。当一个操作遍历这个数据结构时，在递归到下一层次前，其在每一层耗费常数时间。

一个给定的值x在簇编号x／√u中，如果把x看做lgu位的二进制整数，那么簇编号x／√u由x中最高lgu／２位决定。在x簇中，x出现在位置xmod√u中，是由x中最低lgu／２位决定。定义以下一些函数：

high(x) =x / √ulow(x) =x mod √uindex(x,y) =x√u ＋ y

函数high(x)给出了x的簇号。函数low(x)给出了x在它自己簇的位置，y为编号中最低的lgu／２位。恒等式x＝index(high(x)，low(x))。这些函数中使用的u值始终为调用这些函数的数据结构的全域大小，u的值随递归结构改变。

原型van Emde Boas结构

对于全域｛０，１，２，•••，u－１｝，定义原型van Emde Boas结构或proto－vEB结构，记作proto－vEB(u)，可以如下递归定义。每个proto－vEB(u)结构都包含一个给定全域大小的属性u。另外，它包含以下特征：

如果u＝２，那么它是基础大小，只包含一个两个位的数组A[0..1]。否则，对某个整数u≥４，除了全域大小u外，proto－vEB(u)还具有以下属性：

一个名为summary的指针，指向一个proto－vEB(√u)结构。一个数组cluster[１..√u－１]，存储√u个指针，每个指针都指向一个proto－vEB(√u)结构。

元素x递归的存储在编号为high(x)的簇中，作为该簇中编号为low(x)的元素，这里０≤x≤u。

原型van Emde Boas结构上的操作

判断一个值是否在集合中

需要在适当的proto－vEB(２)结构中找到相应于x的位。下面的过程以一个proto－vEB结构V和一个值x作为输入，返回一个位值表示x是否在V包含的动态集合中。

PROTO_vEB_MEMBER(V,x)if V.u ＝=２return V.A[x]elsereturn PROTR_vEB_MEMBER(V.cluster[high(x)],low(x))

第４行处理递归情形，“钻入“到相应更小的proto－vEB结构。值high(x)表示要访问的proto－vEB(√u)结构，值low(x)表示要查询的proto－vEB(√u)结构中的元素。

查找最小元素

过程PROTO_vEB_MINIMUM(V)返回proto－vEB结构V中的最小元素；如果V代表的是一个空集，则返回NIL。

if V.u ==2if V.A[0] == 1return 0else if V.A[1] == 1return 1elsereturn NILelsemin_cluster =PROTO_vEB_MINIMUM(V.summary)if min_cluster ＝=NILreturn NILelseoffset =PROTO_vEB_MINIMUM(V.cluster[min_cluster])return index(min_cluster,offset)

查找后继

过程PROTO_vEB_SUCCESSOR(V,x)返回proto－vEB结构V中大于x的最小元素；或者，如果V中不存在大于x的元素，则返回NIL。

PROTO_vEB_SUCCESSOR(V,x)if V.u == 2if x == 0 and V.A[1] == 1return 1elsereturn NILelseoffset =PROTO_vEB_SUCCESSOR(V.cluster[high(x)],low(x))if offset ≠ NILreturn index(high(x),offset)elsesucc_cluster =PROTO_vEB_SUCCESSOR(V.summary,high(x))if succ_cluster ＝=NILreturn NILelseoffset =PROTO_vEB_MINIMUM(V.cluster[succ_cluster])return index(succ_cluster,offset)

插入元素

要插入一个元素，需要将其插入相应的簇中，并还要将这个簇中的summary位设为１。

PROTO_vEB_INSERT(V, x)if V.u == 2V.A[x] = 1elsePROTO_vEB_INSERT(V.cluster[high(x)],low(x))PROTO_vEB_INSERT(V.summary,high(x))

删除元素

删除操作比插入操作要更复杂些。当插入新元素时，插入时总是将一个summary位置为１，然而删除时却不总是将同样的summary位置为０.需要判断相应的簇中是否存在为１的位。对于已定义的proto－vEB结构，本来需要检查簇内的所有√u位是否为１。取而代之的是，可以在proto－vEB结构中添加一个属性n，来记录其拥有的元素个数。

van Emde Boas树及其操作

把一个数的lgu位分割成最高lgu／２位和最低lgu／２位。为了方便起见，把前者记为↑√u(u的上平方根)，后者记为↓√u(u的下平方根)。重新定义这些函数：

high(x) =x / ↓√ulow(x) =x mod ↓√uindex(x, y) =x * ↓√u + y

van Emde Boas树结构

将全域大小为u的vEB树记为vEB(u)。如果u不为2的基础情形，那么属性summary指向一棵vEB(↑√u)树，而且数组cluster[0..↑√u-1]指向↑√uvEB(↓√u)树。一棵vEB树含有proto-vEB结构中没有的两个属性：

min存储vEB树中的最小元素。max存储vEB树中的最大元素。

存储在min中的元素 并不出现在任何递归的vEB树中，这些树是由cluster数组指向他们的。当一棵vEB树中包含两个或两个以上元素时，我们以不同的方式处理min和max：存储在min中的元素不出现在任何的簇中，而存储在max中的元素却不是这样。

van Emde Boas树的操作

查找最小元素和最大元素、

最小元素和最大元素分别存储在min和max属性中。

vEB_TREE_MINIMUM(V)return V.min

vEB_TREE_MAXIMUM(V)return V.max

判断一个值是否在集合中

直接检查x是否等于最小元素或者最大元素。由于vEB树并不像proto-vEB结构那样存储位信息，涉及vEB_TREE_MEMBER返回TRUE或FALSE而不是0和1。

vEB_TREE_MEMBER(V, x)if x == V.min or x == V.maxrerurn TRUEelse if V.u == 2return FALSEelsereturn vEB_TREE_MEMBER(V.cluster[high(x)], low(x))

查找后继和前驱

回想过程PROTO_vEB_SUCCESSOR(V, x)要进行两个递归调用：一个是判断x的后继是否和x一样被包含在x的簇中；如果不包含，另一个递归嗲用就是要找出包含x后继的簇。由于能在vEB树中很快地访存最大值，这样可以避免进行两次递归调用，并且使一次递归调用或是簇上的或是summary上的，并非两者同时进行。

vEB_TREE_SUCCESSOR(V, x)if V.u == 2if x == 0 and V.max == 1return 1elsereturn NILelse if V.min ≠ NIL and x < V.minreturn V.minelse max_low vEB_TREE_MAXIMUM(V>cluster[high(x)])if max_low ≠ NIL and low(x) < max_lowoffset = vEB_TREE_SUCCESSOR(V.cluster[high(x)], low(x))return index(high(x), offset)elsesucc_cluster = vEB_TREE_SUCCESSOR(V.summary, high(x))if succ_cluster == NILreturn NILelseoffset = vEB_TREE_MINIMUM(V.cluster[succ_cluster])return index(succ_cluster, offset)

寻找前驱和寻找后继的过程是对称的，但是多了一种附加情况。

vEB_TREE_PREDECESSOR(V, x)if V.u == 2if x == 1 and V.min == 0return 0elsereturn NILelse if V.max ≠ NIL and x > V.maxreturn V.maxelsemin_low = vEB_TREE_MINIMUM(V.cluster[high(x)])if min_low ≠ NIL and low(x) > min_lowoffset = vEB_TREE_PRDECESSOR(V.cluster[high(x)], low(x))return index(high(x), offset)else pred_cluster = vEB_TREE_PREDECESSOR(V.summary, high(x))if pred_cluster == NILif V.min ≠ NIL and x > V.minreturn V.minelsereturn NILelseoffset = vEB_TREE_MAXIMUM(V.cluster[pred_cluster])return index(pred_cluster, offset)

插入一个元素

当插入一个元素时，在操作的簇中要么已经包含另一个元素，要么不包含任何元素。如果簇已经包含另一个元素，那么簇编号已经存在于summary中，因此不需要进行递归调用。如果簇不包含任何元素，那么即将插入的元素成为簇中唯一的元素，所以我们不需要进行一次递归来将元素插入一棵空vEB树中。

vEB_EMPTY_TREE_INSERT(V, x)V.min = xV.max = x

vEB_TREE_INSERT(V, x)if V.min == NILvEB_EMPTY_TREE_INSERT(V, x)else if x < V.minexchange x with V.minif V.u > 2if vEB_TREE_MINIMUM(V.cluster[high(x)] == NILvEB_TREE_INSERT(V.summary, high(x))vEB_EMPTY_TREE_INSERT(V.cluster[high(x)], low(x))elsevEB_TREE_INSERT(V.cluster[high(x)], low(x))if x >V.maxV.max = x

删除一个元素

过程vEB_TREE_DELETE(V, x)假设x是vEB树所表示集合中的一个元素。

if V.min == V.maxV.min = NILV.max = NILelse if V.u == 2if x == 0V.min = 1elseV.min = 0V.max = V.minelseif x == V.minfirst_cluster = vEB_TREE_MINIMUM(V.summary)x = index(first_cluster, vEB_TREE_MINIMUM(V.cluster[high(x)]))V.min = xvEB_TREE_DELETE(V.cluster[high(x)], low(x))if vEB_TREE_MINIMUM(V.cluster[high(x)]) == NILvEB_TREE_DELETE(V.summary, high(x))if x == V.maxsummary_max = vEB_TREE_MAXIMUM(V.summary)if summary_max == NILV.max = V.minelse V.max = index(summary_max, vEB_TREE_MAXIMUM(V.cluster[summary_max])else if x == V.maxV.max = index(high(x), vEB_TREE_MAXIMUM(V.cluster[high(x)])