我们知道平衡树在O(log n)时间内执行插入、删除和搜索，示例包括
但是，当键是某个有限范围内的整数时，可以使用 Van Emde Boas 树将这些操作降低到O(log(log n))时间，即比 AVL 或 RB 树成倍地好。嗯，这实际上是许多现实世界应用程序的情况。
我看到很多应用程序。我想引用的一个是数据库，创建索引基本上涉及在哈希或 B*-树之间进行选择。如果实现了 Van Emde Boas 树，它将提供这两个选项之间的折中，理论上可以改善许多查询优化问题。
为什么 Van Emde Boas 树没有像红黑树或 B 树那样被广泛使用，因为
以及对此有何考虑？
渐近复杂度有时会产生误导。Van Emde Boas tree在常数相当大的情况下，请参见此处。我引用：
However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)
在其他情况下，存在具有更好复杂性的算法，但只有在输入如此之大以致在实践中几乎从不使用它时才会变得更好，例如线性时间静态 RMQ。
原因之一是复杂性不是根据您存储的集合的大小来定义的，而是根据值域的大小来定义的。另一个区别是键不能是具有比较操作的任意类型，但必须是整数。您不应将 vEB 视为 BST 的替代品，而应将其视为数组的替代品。数组具有 O(1) 存储和查找以整数为键的对象的成本。vEB 提供 O(log log M)，其中 M 是您的值的大小。现在，您看到 vEB 在查找和存储方面并不比常规数组好，但它提供 O(1) 最小、最大操作和 O(log log M) prev next 关键操作，而数组没有。值得一提的是，vEB 树的布局有一个特性，可以创建缓存遗忘树，这是现代 CS 中更有趣的发展。