van Emde Boas Tree中的高位和低位

Question

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

请解释我哪里出错了？

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

在这里,我们研究了根的树1号,{3},并发现它的最大不大于3,我们发现1 AUX数据结构,这是2的继任者,并返回二路子树的分,这是6.