问题标签 [van-emde-boas-trees]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
data-structures - van Emde Boas Tree 中的高位和低位
我试图理解 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;
请解释我哪里出错了？
data-structures - van Emde Boas 树的最大元素是否应该存储在树外？
我们不需要像对待 min 元素一样对待 max 元素吗？为什么我们可以有这种不对称性并且仍然在 0(loglogN) 时间内执行操作？最大元素沿树传播，但最小元素不会...反转的情况是否有可能有时间进行操作？
我在这里找到：http ://code.google.com/p/libveb/wiki/Intro 我们需要存储它，因为元素的 sqrt 是耗时的操作。但我认为还有别的东西。
language-agnostic - van Emde Boas 树的应用？
除了作为整数的快速优先级队列之外，还有van Emde Boas 树的应用吗？
java - 在构造函数中使用递归是不好的做法吗？
我正在实现 van Emde Boas 树，并且遇到了在构造函数中使用递归非常有用的情况。
当我在树中创建根节点时，该节点将具有指向许多其他节点的指针，这些节点将指向许多其他节点，依此类推。即使这些是用空数据初始化的，我仍然希望它们都在那里。
编辑：在回答评论时，我认为这可能是不好的做法，因为我们在分配内存时总是需要小心。在这种情况下，用户可能不知道分配新的此类节点可能产生的影响，因此他们可能会分配比预期更多的内存？除此之外，我认为在构造函数中分配内存似乎很奇怪/危险。
代码递归地创建新节点，直到创建完整的树。这是一个不好的做法吗？如果是这样，有没有更好的方法在 Java 中做到这一点？
data-structures - 是什么阻止了 Van Emde Boas 树在实际应用中更受欢迎？
我们知道平衡树在O(log n)时间内执行插入、删除和搜索，示例包括
- 红黑
- AVL
- 展开
- B 树（及其变体）。
但是，当键是某个有限范围内的整数时，可以使用 Van Emde Boas 树将这些操作降低到O(log(log n))时间，即比 AVL 或 RB 树成倍地好。嗯，这实际上是许多现实世界应用程序的情况。
我看到很多应用程序。我想引用的一个是数据库，创建索引基本上涉及在哈希或 B*-树之间进行选择。如果实现了 Van Emde Boas 树，它将提供这两个选项之间的折中，理论上可以改善许多查询优化问题。
为什么 Van Emde Boas 树没有像红黑树或 B 树那样被广泛使用，因为
- 这不是什么新鲜事（它是 1975 年发明的）
- 易于实施
- 比其他树快得多
以及对此有何考虑？