Высокие и низкие биты в ван Эмде Боас Три - PullRequest
Новая
       7

Высокие и низкие биты в ван Эмде Боас Три

1 голос
/ 09 декабря 2011

Я пытался понять концепцию дерева vEB.

В примере: Я предположил, что множество юниверсов U = {0, 1, 2, 3 ..... 8}. Итак, размер 9.

Теперь давайте возьмем подмножество S = {0, 1, 3, 4, 6, 7}.

Для операции FindSuccessor (3, S); где мне нужно знать наименьший элемент> 3 в подмножестве S, мне нужно знать старшие и младшие биты моего элемента, то есть 3.

В одном объяснении говорится, что это первая половина и вторая половина бита, что дает результат 00 и 11 как высокий и низкий соответственно.

Другой говорит:

высокий = этаж [элемент / sqrt (| U |)] = этаж [3 / sqrt (9)] = этаж [1] = 1;

низкий = элемент% sqrt (| U |) = 3% sqrt (9) = 0;

Пожалуйста, объясните, где я иду не так?

1 Ответ

6 голосов
/ 11 декабря 2011

Вы не ошибетесь - объяснения для двух немного разных структур данных, которые совпадают только тогда, когда | U | квадратная степень двух. На высоком уровне мы пытаемся разделить ключ k на две половины, каждая с примерно √ | U | возможности. Первый метод достигает этой цели напрямую; второе - это приближение, которое работает быстрее на аппаратном оборудовании (при условии, что | U | - это степень двойки, наихудший случай - когда | 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.

...