是什么阻止了Van Emde Boas树在实际应用中更受欢迎？

Question

我们知道平衡树在O(log n)时间内执行插入,删除和搜索,例如包括

• 红黑
• AVL
• 张开
• B树(及其变体).

但是,当键是在某个有限范围内的整数时,可以使用Van Emde Boas树将这些操作降低到O(log(log n)) - 时间,即指数地优于AVL或RB树.嗯,这实际上是许多现实世界应用程序的情况.

我看到很多应用程序.我想引用的是数据库,创建索引主要涉及在Hash或B*-tree之间进行选择.如果实现了Van Emde Boas树,它将提供这两个选项之间的中间点,理论上可以改善许多查询优化问题.

为什么Van Emde Boas树从未被广泛用作红黑或B树

• 这不是一个新奇事物(它发明于1975年)
• 易于实施
• 比其他树快

有什么考虑呢？

Answer 1

渐近的复杂性有时会产生误导.在Van Emde Boas tree常数相当大的情况下看这里.我引用:

However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)

还存在其他情况,其中存在具有更好复杂度的算法,但是对于如此大的输入仅更好以至于在实践中它几乎从不使用例如线性时间静态RMQ.

Answer 2

其中一个原因是复杂性不是根据您存储的集合的大小而是根据值的范围大小来定义的.另一个区别是键不能是您具有比较操作但必须是整数的任意类型.您不应该将vEB视为BST的替代方案,而是作为数组的替代方案.数组具有O(1)存储并查找由整数键入的对象的成本.vEB提供O(log log M),其中M是您的值的范围的大小.现在,您看到vEB并不比常规数组更好地用于查找和存储,但它提供O(1)min,max操作和O(log log M)prev下一个键操作,而数组则没有.值得一提的是,vEB树的布局具有一些属性,这些属性可以创建缓存遗忘树,这是现代CS更有趣的发展.

http://erikdemaine.org/papers/BRICS2002/paper.pdf