(对于一些简单的数据结构，我就不写在博客上了，然而这个van Emde Boas 树是真的有问题。。）
首先，先介绍在本章中n与u的用法：
n：集合中当前元素的个数；
u：元素可能的取值范围；
同时，该数据结构将关键字限制在 0 ~ n - 1中（与计数排序有相似性）
1、基本方法
1、位向量：A[0……u - 1]，其中每个位置存储的是该位置上的元素是否存在。
2、叠加的二叉树结构：
其中，每个结点存储的是其儿子结点是否存在的逻辑或，即：若两个儿子都不存在，则为0，否则为1.
3、叠加的一棵高度恒定的树
设全域大小 u = 2^(2k)， 其中k∈N*，则u^(1/2) = 2^k依然为整数，此时，我们叠加的便是一棵度数为u^(1/2)的树。可以预想到，树的高度恒定为2：由一个根生成u^(1/2)个孩子，而这些孩子又拥有同样数目的孩子，并且，他们的孩子就是存储在数据中的位向量，共u个。
其中，根结点的儿子层也用一个summary[0，u^(1/2) - 1]的数组存储起来。同时将其中每个结点 i 对应的叶节点的A[ iu^(1/2)……(i + 1)u^(1/2) - 1]称为簇（cluster)。
2、递归结构
对于以上叠加的方法，此时使用递归的方式：以上次的平方根缩减树的大小：
对于全域 u = 2^ (2^k)，则第一次缩减后，每个结点所包含的项数为u^(1/2) = 2^(2^k / 2) = 2^(2^(k - 1))，同时，该层包含的结点的个数为二者之商，得到4个；第二次缩减后的项数为2^(2^(k - 2))，结点总个数为 16。并以此类推，因此，在位于位数组的上面的一层的结点数为lg u = 2 ^ k 个结点，并由此计算出此时每个结点应该包含的儿子数为：2^m/m，其中m = 2 ^ k。
此时再回到高度恒定的树上，对于值x，A[ x ]位于编号⌊x/u(1/2)⌋中。若将x看作lgu位的二进制整数， 大于lgu / 2的位决定它应该处于的簇中，小于lg u / 2 的位决定它在簇中所取得的位置。并同时有以下定义：
high(x) =⌊x/(u^(1/2))⌋决定其簇号。
low(x) = x mod u^(1/2) 决定它在簇中所取得的位置，
index(x, y) = xu^(1/2) + y，有恒等式：x = index(high(x), low(x))。
1、proto Emde Boas 树
首先，我们定义原型van Emde Boas结构（proto-vEB structure)，记作proto-vEB(u)，其中u是全域{0……u - 1}。特征如下：
1、若 u = 2，那么它是基础的结构，仅包含一个两个位的位数组A[1]。
2、若 u > 2，那么对k ≥ 1，，则有 u ≥ 4，除全域 u 外，它具有：
a、一个名为summary的指针，指向一个的结构。（注：此summary仅表示簇中的逻辑关系或，并不指向相关的位元素。
b、一个名为cluster[1……- 1]的指针数组，即它存储个指针，其中每个指针指向一个proto-vEB(）结构。
注：它没有了位数组A[1]。
笔者觉得，既然是树的结构，那么书中的图应该更贴近于树的样子，然而实际上它并没有这样做，因此笔者手动归纳了一个总域 u = 16的情形。（手写，很丑，见谅，俺也不知道为何是歪的。。。）
其中，大部分需要注意的已经标记在上面，同时，pvEB是proto-van Emde Boas树的简写。此外还有需要注意的：
1、cluster数组存储的是指向pvEB结构的指针，它里面并没有存储数据——除了指向下一个结构的指针，我们也需要通过它来访问最底层的位数组。
2、图中，由summary形成的或逻辑树中的每个结点都存放两个元素，而这实际上是一种巧合，对于 u = 256 的话，情形并非如此。
2、pvEB上的操作
是否在集合中：
proto_vEB_Member(V, x)if V.x == 2return V.A[x];else return proto_vEB_Member(V.cluster[high(x)], low(x));
查找最小元素：
Proto_vEB_Minimum(V)if V.u == 2if V.A[0] == 1return 0;else if V.A[1] == 1return 1;else return NIL;else min_cluster = Proto_vEB_Minimum(V.summary)if min_cluster == NILreturn NIL;else offset = Proto_vEB_Minimum(V.cluster[min_cluster]);return index(min_cluster, offset);
在明确这个算法的目的前，我们再确认一次：每个PvEB结构中的summary递归指向的最小 u = 2 的PvEB结构的集合，存储的该PvEB的簇的编号。
之后回到该算法：先对基础情形进行判断：在 u = 2时为基础情形，此时根据位数组A存储的数据来判断应该返回的值。
其中的情形从先到后如上代码所示，其中，当两者皆为0时，返回NIL——因为该数组啥也没有。
在非基础情形，即 u ＞2 时，我们先对V.summary递归调用该函数，找到最小的簇的编号。在此处有两点需要注意：
1、为什么是递归调用：因为我们并不确定该V.summary是最小的结构，此时它也可能 u = 4，因而还会继续产生一个summary和两个簇。这两个最基本的簇才是与最初的V.cluster的编号相对应。而此时生成的summary则与同一个PvEB结构中的簇号相对应。而此时，对最底层的summary进行调用时，将符合u = 2的情形；返回的将指示次一层cluster的簇号，而此时由于 u = 4 > 2，同时它会通过offset在最小的簇中查找偏移量，并返回这个偏移量与该结构中最小簇的index运算，这个量就是最初的pvEB结构中最小元素所在的簇号（注：对应于在最底层中最小的A[ x ] = 1的x值，无论是A1还是A2）。此时便又回到最上层的summary的Proto_vEB_Minimum调用。
2、NIL情形的出现：在该算法中，我们多次看到了NIL的出现：无论是在u = 2的基础情形中，或是 min_cluster 的非基础情形中，那么出现了一个问题：NIL会在什么情况下出现。
首先，我们根据算法中变量含义：min_cluster指示最小元素所在的簇号，当它不存在，或者同时最底层的位数组两个均为0的情况下会出现NIL结果。那么不难推断出当集合中所有元素均不存在时将返回NIL。
这个结论的证明也并不是很难，考虑在对offset设定：它在min_cluster存在的情况下对其调用Minimum函数，此时，簇将存在，不会出现NIL情形。出现NIL情形的有：min_cluster为NIL，此时所有簇的元素都不存在，即上述表示。
关于运行时间，书上表述的十分清楚。
查找后继：
Proto_vEB_Successor(V, x)if V.u == 2if x == 0 && V.A[1] == 1return 1;else return NIL;else offset = Proto_vEB_Successor(V,cluster[high(x)], low(x));if offset != NILreturn Index(high(x), offset);else succ_cluster = Proto_vEB_Successor(V.summary, high(x))if succ_cluster == NILreturn NILelse offset = Proto_vEB_Minumm(V.cluster[succ_cluster]);return Index(succ_cluster, offset);
在有了查找最小元素的基础后，理解该方法也不是那么困难了：首先考虑基础情形，到了某一层，u = 2，此时则仅在x = 0，且A[1]存在的情况下 返回该 1。这并不难理解，不过，问题是，为什么我们必须在与 x 在同一个簇中寻找它的后继呢，为啥不在下一个簇中寻找呢？这个问题的解答就在下方的 succ_cluster 行中。不过先让我们继续按算法编写的顺序分析它：
现在考虑非基础情形：当 u > 2 时，此时，进入到第一个else，它计算offset——得出在当前层数所对应结点所在的簇中的号数。此时我们将Proto_vEB_Successor想象成我们已经实现了的抽象，则它在它的 cluster[ high(x) ] 寻找 low(x) 的后继，如果得到了答案，那么将返回这个答案。此时，我们依然没有解决最初提到的问题。
不过，在 offset = NIL 的时候，我们将解决这个这个问题。它表明并没有寻找到相当应的后继——即在刚才对于在簇号为high(x)中寻找后继返回的结果为NIL，那么此时，x 的后继并不在这个簇中，那么我们需要找到它后继所在的簇号，此时我们在V.summary中寻找下一个簇号，此时我们依然借用了对函数自身的抽象。若都没有找到下一个簇，那么自然就会返回NIL，否则我们就可通过Proto_vEB_Minimum来找到这个簇中最小的元素，之后通过返回Index即可。
最后，讨论抽象是否成立，这表明我们必须考虑到所有的情况。首先，我们根据了 u 的大小进行讨论 u = 2 即时基础情形； u > 2时，我们分别讨论了能和不能在该簇中找到它的后继的情形，若能，则直接对该簇调用该函数，否则就寻找下一个含有元素的簇。当然，实际上我们是先计算再讨论。
插入元素
Proto_vEB_Insert(V, x)if V.u == 2V.A[x] = 1else Proto_vEB_Insert(V.cluster[high(x)], low(x))Proto_vEB_Insert(V.summary,high(x))
这个十分简单，没什么好说的。
删除元素
Proto_vEB_Delete(V, x)if V.u == 2V.A[x] = 0else Proto_vEB_Delete(V.cluster[high(x)], low(x));Proto_vEB_Adjust(V,x);Proto_vEB_Delete(V.summary, high(x));Proto_vEB_Adjust(V.summary,x);Proto_vEB_Adjust(V, x)if V.u == 4if V.cluster(high(x)).A[!low(x)] == 0V.summary.A[high(x)] = 0;else Proto_vEB_Adjust(V.cluster[high(x)], low(x));Proto_vEB_Adjust(V.summary);
在该函数中，首先保留insert中所执行的操作，不过将V.A[ x ] = 1 换为 V.A[ x ] = 0。
但是，由于对x结点的改变，会改变相应summary中对应簇中的存储信息。要注意的是，在此时的基础情形是 u = 4，因为 u = 2 的基础情形已经在Delete函数中讨论过了。此时该pvEB具有两个簇以及一个sum，我们需要对x所在的簇所对应的summary中的A数组的相应位进行调整。实现为Adjust函数的2、3行。
对于非基础情形，我们此时假定最小情况， u = 16以便于分析，此时的x位于4个簇中的某一个，我们需要调整的是summary中的该簇以及在该簇中的summary，无论是哪种情况，则又会到基础情形。
