标签: van-emde-boas-trees

我们知道平衡树在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年)
• 易于实施
• 比其他树快

有什么考虑呢？

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

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

是否存在任何(可能是商业的)vEB树或y-fast尝试或类似数据结构的库？

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

我试图理解vEB树的概念.

在一个例子中:我假设宇宙集U = {0,1,2,3 ...... 8}.所以大小是9.

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

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

一个解释是它的前半部分和后半部分,分别将结果00和11分别设为高和低.

另一个说:

high = Floor [element/sqrt(| U |)] = Floor [3/sqrt(9)] = Floor [1] = 1;

low = element%sqrt(| U |)= 3%sqrt(9)= 0;

请解释我哪里出错了？