vEB tree算法简介

vEB tree算法简介

vEB tree是VAN EMDE BOAS Tress的缩写，是一种 时间复杂度为O(lglgU) 的查找算法。基于比较操作的查找算法最佳时间复杂度为O(lgn)，vEB tree算法借用了一些 位操作 的技巧，将时间复杂度降低为O(lglgn)，所以在问题规模相对问题空间较大的情况下有较好的表现。它是由一个荷兰计算机学家Peter van Emde Boas领导的团队在1975年发明的。参考文献如下，如果链接过期了的话也可以根据论文名字重新搜索。
van Emde Boas, Peter. “Preserving order in a forest in less than logarithmic time.” 16th Annual Symposium on Foundations of Computer Science (sfcs 1975). IEEE, 1975.
另外作者在1977年改进了算法，将空间复杂度降低为线性，参考文献如下。
van Emde Boas, Peter. “Preserving order in a forest in less than logarithmic time and linear space.” Information processing letters 6.3 (1977): 80-82.

引子:传统的二分查找

问题:
给定一个递增的序列x[n]，用二分查找数值a是否存在序列当中。
解答：

1. 取序列二分点的数值和a对比，如果二分点的数值等于a，或序列长度为1则结束。
2. 如果二分点大于a，则去掉序列后半段，否则去点序列前半段，返回1步。

以上就是典型的二分查找，每次都把序列对半分，直到序列长度为1，最坏的情况下可能操作x次。即:

$$n(\frac{1}{2})^x=1$$

显然:

$$x=log_2^n$$

接下来思考一个问题， 如果每次不是二分，而是多分 是不是可以算的更快呢？

vEB tree算法

数据存储在计算机当中是二进制的，计算机对数据的运算最终都是执行一些位操作。如果考虑位操作的话，其实每次是可以将数据$\sqrt n$分的。考虑数字16，可以分解为4x4，4是 $2^2$二进制是0B 100，16是$2^4$二进制表示l是0B 10000，刚好是0B 100乘方的结果。
假设有为0-15，共16个数，那么把这16个数全部用二进制表示如下：

可以看到如果把二进制表示的数前后各两个比特位拆开，前两个比特位相同的数字合为一段，可以把大小为16的空间拆分成$\sqrt16$即4段。后两个比特位则可以表示数字在段当中的位置。比如数字9，拆分后，属于0B 10段，在段中的0B 01位。
另外再说明一下问题空间U和问题规模n，如上述例子，所有的数都在0-15范围内，问题空间U就是16。假设查找其中的2、4、11，三个数，问题规模n就是3。
现在vEB tree的核心思想就可以理解了，将要查找的数据按照二进制对半分(高位补零)，前半部分为段值，后半部分为段内的位置。再段内位置作为问题空间递归的查找下去，直到找到或者问题空间大小为2为止。
举个例子，问题空间为256，查找数字7。二进制7为0B 0000 0111(高位补零)，首次查找在0B 0000段，段内0B 0111位置。将段内位置作为问题空间递归查找，二次查找在0B 01段，段内0B 11位置。三次查找，在0B 1段，段内0B 1位置。查找结束。
以上就是最朴素的vEB tree思想的查找方法，每次都把问题空间开方分，直到问题空间为2，最坏的情况下可能操作x次。即:

$$U^{\frac{1}{2^x}}=2$$

显然:

$$x=log_2^{log_2^U}$$

vEB tree的数据结构

vEB tree是递归定义的，所以实际上vEB tree的数据结构很简单，只需要理解一个节点就可以了。
一个节点就是一个$\sqrt U$叉树，每个分支就是一个段，分支的值是一个指针，指向下一级节点。
每个节点包含两个特殊变量，最大值和最小值，表示这个节点以及它之下子节点存储的值当中的最大和最小值，如果是负数，则表示这个节点是空节点。

节点{
  最大值
  最小值
  子节点1
  …
  子节点n
}

以上就是vEB tree的基本思想，更详细的介绍可以参考机械工业出版社的《算法导论》。
vEB tree的基本操作时间复杂度都是O(lglgU)，所以对于在问题空间当中分布密集的数据有很好的表现。不过由于关键字限制在0-U之间，所以实际应用范围有限。
另外现在看起来vEB tree的空间复杂度是O(U)，实际上通过哈希，可以降低到O(n)。