是什么阻止Van树在现实世界中更受欢迎呢？

Question

我们知道平衡树在O(log )-time中执行插入、删除和搜索，示例包括

• 红黑
• AVL
• 张扬
• B树(及其变体)。

但是，当键是有限范围内的整数时，可以使用Van树将这些操作降到O(log(log ))-time，即比AVL或RB树的指数更好。实际上，这是许多实际应用程序的情况。

我看到了很多这样的申请。我想举一个例子，在数据库中，创建索引基本上包括在Hash和B*-树之间进行选择。如果实现了Van树，它将在这两个选项之间提供一个中间部分，理论上改进了许多查询优化问题。

为什么Van Emde Boas树没有被广泛用作红-黑或B-树

• 这不是什么新鲜事物(它是1975年发明的)
• 易于实现
• 比其他树木快得多

对此有什么考虑呢？

Answer 1

渐进的复杂性有时是误导的。在Van Emde Boas tree的情况下，常数是相当大的see here。我引述如下：

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 )，其中M是值的宇宙大小。现在，您可以看到，vEB在查找和存储方面并不比常规数组好，但是它提供了O(1) min、max操作和O(log M) prev下一个数组没有的键操作。值得一提的是，vEB树的布局具有创建缓存遗忘树的特性，这是现代CS的更有趣的发展。

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