1

vEB ツリーの概念を理解しようとしていました。

例: ユニバース セット U = {0, 1, 2, 3 ..... 8} を仮定しました。なのでサイズは9号。

ここで、サブセット S = {0, 1, 3, 4, 6, 7} を取ります。

オペレーションの場合、FindSuccessor (3, S); サブセット S で 3 を超える最小の要素を知る必要がある場合、要素の上位ビットと下位ビット、つまり 3 を知る必要があります。

1つの説明は、前半と後半のビットであり、結果00と11をそれぞれハイとローとして与えます。

別の言い方：

高 = 床 [要素/平方(|U|)] = 床 [3/平方 (9)] = 床 [1] = 1;

低 = 要素 % sqrt(|U|) = 3 % sqrt (9) = 0;

どこが間違っているのか説明してください。

4

1 に答える 1

6

|U| の場合にのみ一致するわずかに異なる 2 つのデータ構造についての説明です。は 2 の平方乗です。大まかに言うと、キー k を 2 つの半分に分割しようとしています。それぞれの部分は約 √|U| です。可能性。最初の方法は、この目標を直接達成します。2 番目は、コモディティ ハードウェアでより高速に実行される近似です (|U| が 2 のべき乗であると仮定すると、最悪のケースは |U| が正方形ではなく、前半が 2 番目の 2 倍の可能性を持つ場合です)。1 つの方法を選択し、それを固守します。

FindSuccessor(3, S) の例を次に示します。簡単にするために、3 つの要素で再帰を底上げします。

木は次のように見えます

       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 を計算します。ツリーに 3 つ以上のレベルがある場合は、再帰的に検索します)。

より興味深いケースは、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 を超えていないことを発見しました。補助データ構造で 1 の後続の 2 を見つけ、2 番目のサブツリーの最小値を返します。 、これは 6 です。

于 2011-12-11T02:27:32.657 に答える