1

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

请解释我哪里出错了？

4

1 回答 1

6

你不会错的——这些解释是针对两个稍微不同的数据结构，它们仅在 |U| 时才会重合。是二的平方幂。在高层次上，我们试图将密钥 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

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

于 2011-12-11T02:27:32.657 回答