我将按四个步骤来逐一引入到van Emde Boas树。从位图到索引位图，再到van Emde Boas原型，最后到van Emde Boas树。

位图与索引位图

  在java中有这个一个类，叫EnumSet。这个类只能存储枚举类型。枚举有个明显的特征，就是取值范围限定在有限个元素内，比如星期一到星期天可以用枚举来表示。EnumSet这个类的实现原理是位图，用每个位来表示元素是否存在，这样不仅节省了存储空间，也使得插入、删除操作性能非常高，时间复杂度为$O(1)$。
  但是位图存在一个缺点，就是最小值minimum、最大值maximum、前任predecessor、后任successor这四种操作操作时间复杂度比较大。
  为了提高这四种操作的性能，可以在位图上建立二叉树索引。二叉树每个节点取值只有两种，0或1。取值的依据是底层两个子节点的或运算结果，这样就可以知道子节点到底有没有某个元素。这样能更加快速地寻找最小值、最大值、前任、后任等。如下图所示,是找前任的搜索路径：

  可以看到性能比较慢啊，虽然某些情况下比在位图上按顺序检索快一点，比如上图中找O的前任。但这不是我们想要的东西。

van Emde Boas原型

  van Emde Boas原型proto van Emde Boas，是一种二进制结构。它是一种二进制结构，是在位图索引的基础上发展而来的。
  先试想一下，降低层数，会是什么样的效果。
  这种数据结构还不是是van Emde Boas原型结构。但是还不是我们最终需要的东西。但是很接近了。首先我们需要一个数组存储状态。这个新的数据结构节点有三个属性：元素最大数量，子节点统计和子节点数组。如下图所示是只存储偶数节点索引的van Emde Boas原型结构，u代表元素个数（图中是16个），s代表统计数据summary，c代表子节点数组cluster。

  特别注意的是，当u=2时，由于不能继续细分，所以没有了summary和cluster属性。这已经非常接近van Emde Boas树了。
  不同的在于，proto van Emde Boas只支持元素数量为2、4、16、256。也就是按$2^{2^k}$进行膨胀，比如：
$$\begin{gathered} 2^{2^0}=2^1=2 \\ {2}^{2^1}=2^2=4 \\ {2}^{2^2}=2^4=16 \\ {2}^{2^3}=2^8=256 \\ {2}^{2^4}=2^{16}=65536 \\ {2}^{2^5}=2^{32}=4294967296 \end{gathered}$$
  所以van Emde Boas原型结构对元素数量的要求太严苛了。如果元素数量不是这个数，就容易造成内存空间的极大浪费。那怎么办？

van Emde Boas树

  这个时候就需要对van Emde Boas继续改造，变成van Emde Boas树。van Emde Boas树的节点与van Emde Boas原型稍微有点不同。首先是节点多了两个属性min和max。min和max的处理还是有点不同。除min以外的才存储，也就是说min不会存储到任何cluster中。这样设计的目的是为了节省一点存储空间。但要注意，max还是要存的。
  此外，对于最小的尺寸为2的叶子，也是有改变的，因为有min和max两个属性，所以就不需要底层数组了。
  以u=16为例子，存储{2,3,4,5,7,14,15}这几个数据是这样的效果：

  这种结构就节省了一些存储空间。这就是我们最终要的van Emde Boas树。

java代码实现

  git 地址 https://e.coding.net/buildt/data-structure/trees.git