问题标签 [van-emde-boas-trees]

vEB Trees是否有可靠的 C++ 实现？

Boost没有它。这似乎很不寻常。

是否有任何（可能是商业的）用于 vEB 树或 y-fast 尝试或类似数据结构的库？

我试图理解 vEB 树的概念。

在一个例子中：我假设一个全集 U = {0, 1, 2, 3 ..... 8}。所以尺寸是9。

现在让我们取一个子集 S = {0, 1, 3, 4, 6, 7}。

对于一个操作 FindSuccessor(3, S); 我需要知道子集 S 中的最小元素 > 3，我需要知道我的元素的高位和低位，即 3。

一种解释是它的前半部分和后半部分，将结果 00 和 11 分别作为高和低。

另一个说：

高 = 楼层 [元素/sqrt(|U|)] = 楼层 [3/ sqrt (9)] = 楼层 [1] = 1；

低 = 元素 % sqrt(|U|) = 3 % sqrt (9) = 0;

请解释我哪里出错了？

我们不需要像对待 min 元素一样对待 max 元素吗？为什么我们可以有这种不对称性并且仍然在 0(loglogN) 时间内执行操作？最大元素沿树传播，但最小元素不会...反转的情况是否有可能有时间进行操作？

我在这里找到：http ://code.google.com/p/libveb/wiki/Intro 我们需要存储它，因为元素的 sqrt 是耗时的操作。但我认为还有别的东西。

除了作为整数的快速优先级队列之外，还有van Emde Boas 树的应用吗？

我正在实现 van Emde Boas 树，并且遇到了在构造函数中使用递归非常有用的情况。

当我在树中创建根节点时，该节点将具有指向许多其他节点的指针，这些节点将指向许多其他节点，依此类推。即使这些是用空数据初始化的，我仍然希望它们都在那里。

编辑：在回答评论时，我认为这可能是不好的做法，因为我们在分配内存时总是需要小心。在这种情况下，用户可能不知道分配新的此类节点可能产生的影响，因此他们可能会分配比预期更多的内存？除此之外，我认为在构造函数中分配内存似乎很奇怪/危险。

代码递归地创建新节点，直到创建完整的树。这是一个不好的做法吗？如果是这样，有没有更好的方法在 Java 中做到这一点？

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

• 红黑
• AVL
• 展开
• B 树（及其变体）。

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

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

为什么 Van Emde Boas 树没有像红黑树或 B 树那样被广泛使用，因为

• 这不是什么新鲜事（它是 1975 年发明的）
• 易于实施
• 比其他树快得多

以及对此有何考虑？