van Emde Boas树的高位和低位

Question

我试图理解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；

low =元素% sqrt(|U|) =3%sqrt (9) = 0；

请解释一下我哪里错了？

Answer 1

你没有错--解释是针对两种略微不同的数据结构，只有当|U|是2的平方幂时，这两种数据结构才会重合。在更高的层次上，我们试图将密钥k分为两个部分，每个部分都有大约√|U|的可能性。第一种方法直接实现这个目标；第二种方法是在商用硬件上运行更快的近似值(假设|U|是2的幂，最坏的情况是|U|不是正方形，并且前半部分的可能性是后半部分的两倍)。选择一种方法并坚持下去。

下面是FindSuccessor(3，S)的一个例子。为简单起见，我将从三个元素开始递归。

这棵树看起来像

       min=0|  aux
       max=7|------->min=0|
       / | \         max=2|
      /  |  \         /|\
     /   |   \       0 1 2
    /    |    \
   v     v     v
min=0| min=3| min=6|
max=1| max=4| max=7|
 /|     /|     /|
0 1    3 4    6 7

在根部，我们拆分3 = (1，0)，并检查第1个(中间)子级是否有max >3。确实如此，因此我们下降到那里，并使用暴力来计算答案4。(当然，如果树有两个以上的级别，我们将递归搜索。)

更有趣的情况是当S= {0，1，3，6，7}时。

       min=0|  aux
       max=7|------->min=0|
       / | \         max=2|
      /  |  \         /|\
     /   |   \       0 1 2
    /    |    \
   v     v     v
min=0| min=3| min=6|
max=1| max=3| max=7|
 /|     /      /|
0 1    3      6 7

在这里，我们检查根{ 3 }的第1个子树，发现它的最大值不大于3。我们在aux数据结构中找到1的后继子树，即2，并返回第2个子树的最小值，即6。