van Emde Boas樹的高位和低位

我試圖理解vEB樹的概念。van Emde Boas樹的高位和低位

在一個例子中：我假定宇宙集合U = {0,1,2,3 ..... 8}。所以大小是9.

現在讓我們取一個子集S = {0,1,3,4,6,7}。

對於操作FindSuccessor（3，S）;在我需要知道子集S中最小的元素> 3時，我需要知道我的元素的高位和低位，即3.

一個解釋說它的前半部分和後半部分，給出結果00和11分別爲高和低。

另一個表示：

高= FLOOR [元件/ SQRT（| U |）] = FLOOR [3/SQRT（9）] = FLOOR [1] = 1;

low = element％sqrt（| U |）= 3％sqrt（9）= 0;

請解釋我哪裏錯了？

來源

2011-12-09 sg1

你不會錯 - 解釋是兩個稍有不同的數據結構，只有在| 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號（中）孩子是否有最大> 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大，返回第2個子樹的最小值，即6。

來源

2011-12-11 02:27:32 Per

謝謝:) 您可以解釋如何在上面的示例中使用任何一種方法獲取FindSuccessor（3，S）？我有一些麻煩理解它背後的算法。 – sg1

@ sg1好的，添加了幾個例子。 – Per

非常感謝:-) – sg1

van Emde Boas樹的高位和低位

回答

相關問題