Ван Эмде Боас уходит в отставку

шаги ван Эмде Боаса
Тип	Недвоичное дерево
Изобретенный	1975
Изобретён	Питер ван Эмде Боас
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск $O(\log \log M)$ $O(\log \log M)$ Вставлять $O(\log \log M)$ $O(\log \log M)$ Удалить $O(\log \log M)$ $O(\log \log M)$ Пространственная сложность Космос $O(M)$ $O(M)$

Шагает Ван Эмде Боас ( Голландское произношение: [vɑn ˈɛmdə ˈboːɑs] ), также известное как дерево vEB или очередь приоритетов Ван Эмде Боаса , представляет собой древовидную структуру данных , которая реализует ассоциативный массив с m -битными целочисленными ключами. Он был изобретен командой под руководством голландского ученого-компьютерщика Питера ван Эмде Боаса в 1975 году. Он выполняет все операции за время O (log m ) (при условии, что $m$ битовая операция может выполняться за постоянное время) или, что то же самое, за $O(\log \log M)$ время, где $M=2^{m}$ — это самый большой элемент, который может быть сохранен в дереве. Параметр $M$ не следует путать с фактическим количеством элементов, хранящихся в дереве, по которому часто измеряется производительность других древовидных структур данных.

Стандартное дерево vEB имеет недостаточную эффективность использования пространства. Например, для хранения 32-битных целых чисел (т. е. когда $m=32$, это требует $M=2^{32}$ биты памяти. Однако аналогичные структуры данных с одинаково хорошей эффективностью времени и пространства $O(n)$ существуют там, где $n$ — это количество хранимых элементов, а деревья vEB можно изменить, потребовав только $O(n\log M)$ космос.

Поддерживаемые операции

vEB поддерживает операции с упорядоченным ассоциативным массивом , который включает в себя обычные операции с ассоциативным массивом, а также еще две операции с упорядочением , FindNext и FindPrevious :

• Вставить : вставить пару ключ/значение с m -битным ключом.
• Удалить : удалить пару ключ/значение с заданным ключом.
• Поиск : найти значение, связанное с данным ключом.
• FindNext : найти пару ключ/значение с наименьшим ключом, превышающим заданный k.
• FindPrevious : найти пару ключ/значение с наибольшим ключом, который меньше заданного k.

Дерево vEB также поддерживает операции «Минимум» и «Максимум» , которые возвращают минимальный и максимальный элемент, хранящийся в дереве соответственно. Оба они бегут $O(1)$ время, поскольку минимальный и максимальный элементы хранятся как атрибуты в каждом дереве.

Функция

Пример дерева Ван Эмде Боаса с размерностью 5 и дополнительной структурой корня после вставки 1, 2, 3, 5, 8 и 10.

Позволять $\log _{2}m=k$ для некоторого целого числа $k$. Определять $M=2^{m}$. Дерево VEB Т над вселенной $\{0,\ldots ,M-1\}$ имеет корневой узел, в котором хранится массив Т.дети длины ${\sqrt {M}}$. T.children[i] — указатель на дерево vEB, отвечающее за значения $\{i{\sqrt {M}},\ldots ,(i+1){\sqrt {M}}-1\}$. Кроме того, T хранит два значения Тмин и T.max, а также вспомогательное дерево vEB Ставка .

Данные хранятся в дереве vEB следующим образом: Наименьшее значение, находящееся в настоящее время в дереве, сохраняется в T.min и наибольшее значение сохраняются в Т.макс . Обратите внимание, что T.min больше нигде в дереве vEB не хранится, а Т.макс есть. Если T пусто, мы используем соглашение, согласно которому Т.макс=-1 и Т.мин=М . Любое другое значение $x$ хранится в поддереве Т.дети[i] где $i=\lfloor x/{\sqrt {M}}\rfloor$. Вспомогательное дерево T.aux отслеживает, какие дочерние элементы не пусты, поэтому T.aux содержит значение $j$ тогда и только тогда, когда T.children[j] непусто.

НайтиСледующий

Операция FindNext(T, x) , который ищет преемника элемента x в дереве vEB, действует следующим образом: Если x <T.min , то поиск завершен и ответ Т.мин . Если x≥T.max , то следующий элемент не существует, верните M. В противном случае пусть $i=\lfloor x/{\sqrt {M}}\rfloor$. Если x<T.children[i].max , то искомое значение содержится в T.children[i], поэтому поиск продолжается рекурсивно в Т.дети[я] . В противном случае мы ищем преемника значения i в Т.ох. ​Это дает нам индекс j первого поддерева, содержащего элемент больше x . Затем алгоритм возвращает Т.дети[j].мин . Элемент, найденный на дочернем уровне, должен быть составлен из старших битов, чтобы сформировать полный следующий элемент.

функция  FindNext(T, x)     если  x < T.min  , то          вернуть  T.min     если  x ≥ T.max  , то   // следующий элемент не          возвращает  M    я = пол(х/ ${\sqrt {M}}$)    ло = х мод ${\sqrt {M}}$        если  lo < T.children[i].max  , то          верните  ( ${\sqrt {M}}$ i) + FindNext(T.children[i], lo)    j = FindNext(T.aux, i)     возвращаться  ( ${\sqrt {M}}$ j) + T.children[j].min конец 

Обратите внимание, что в любом случае алгоритм выполняет $O(1)$ работать, а затем, возможно, рекурсивно работать по поддереву во вселенной размером $M^{1/2}$ (ан $m/2$ битовая вселенная). Это дает повторение для времени выполнения $T(m)=T(m/2)+O(1)$, что разрешает $O(\log m)=O(\log \log M)$.

Вставить

Звонок Insert(T, x) который вставляет значение x в дерево VEB Т действует следующим образом:

1. Если T пусто, мы устанавливаем T.min = T.max = x , и все готово.
2. В противном случае, если x<T.min , то мы вставляем T.min в поддерево я отвечаю за T.min , а затем установите Т.мин = х . Если T.children[i] ранее был пустым, тогда мы также вставляем я в Ставка
3. В противном случае, если x>T.max , затем вставляем x в поддерево я отвечаю за х , а затем установите Т.макс = х . Если T.children[i] ранее был пустым, тогда мы также вставляем я в Ставка
4. В противном случае, T.min< x < T.max, поэтому мы вставляем x в поддерево я отвечаю за х . Если T.children[i] ранее был пустым, тогда мы также вставляем я в Ставка .

В коде:

функция  Вставка(Т, х)     если  T.min == x || T.max == x  then   // x уже вставлен          return      if  T.min > T.max  then   // T пусто         Т.мин = Т.макс = х;         вернуть,      если  x < T.min,  тогда         своп(х, Т.мин)     если  x > T.max,  то         Т.макс = х    я = пол (х / ${\sqrt {M}}$)    ло = х мод ${\sqrt {M}}$    Вставить(T.children[i], вот)     если  T.children[i].min == T.children[i].max  , то         Вставить(T.aux, я) конец 

Ключом к эффективности этой процедуры является то, что вставка элемента в пустое дерево vEB занимает время O (1) . Таким образом, хотя алгоритм иногда выполняет два рекурсивных вызова, это происходит только в том случае, если первый рекурсивный вызов был обращен к пустому поддереву. Это дает ту же повторяемость времени выполнения $T(m)=T(m/2)+O(1)$ как раньше.

Удалить

Удаление из деревьев vEB — самая сложная операция. Звонок Функция Delete(T, x) , которая удаляет значение x из дерева vEB T, действует следующим образом:

1. Если T.min = T.max = x , тогда x — единственный элемент, хранящийся в дереве, и мы устанавливаем Т.мин = М и T.max = −1, чтобы указать, что дерево пусто.
2. В противном случае, если x == T.min , то нам нужно найти второе наименьшее значение y в дереве vEB, удалить его из текущего местоположения и установить Т.мин=у . Второе наименьшее значение y равно T.children[T.aux.min].min , поэтому его можно найти за время O (1) . Мы удаляем y из поддерева, которое его содержит.
3. Если x≠T.min и x≠T.max , то мы удаляем x из поддерева T.children[i] который содержит x .
4. Если x == T.max , то нам нужно будет найти второе по величине значение y в дереве vEB и установить Т.макс=у . Начнем с удаления x, как и в предыдущем случае. Тогда значение y либо Т.мин или T.children[T.aux.max].max , поэтому его можно найти за время O (1) .
5. В любом из вышеперечисленных случаев, если мы удалим последний элемент x или y из любого поддерева T.children[i] то мы также удаляем i из Ставка .

В коде:

функция  Удалить(T, x)     если  T.min == T.max == x  , то         Т.мин = М        Т.макс = −1         вернуть,      если  x == T.min  , тогда         привет = T.aux.min * ${\sqrt {M}}$        j = T.aux.min        T.min = x = hi + T.children[j].min    я = пол (х / ${\sqrt {M}}$)    ло = х мод ${\sqrt {M}}$    Удалить(T.children[i], вот)     если  T.children[i] пуст  , то         Удалить(T.aux, я)     если  x == T.max  , то          если  T.aux пуст  , то             Т.макс = Т.мин.         еще             привет = T.aux.max * ${\sqrt {M}}$            j = T.aux.max            Т.макс = привет + Т.дети[j].макс конец 

Опять же, эффективность этой процедуры зависит от того, что удаление из дерева vEB, содержащего только один элемент, занимает постоянное время. В частности, второй вызов удаления выполняется только в том случае, если x был единственным элементом в T.children[i] до удаления.

На практике

Предположение о том, что log m является целым числом, не является необходимым. Операции $x{\sqrt {M}}$ и $x{\bmod {\sqrt {M}}}$ можно заменить, взяв только биты высшего порядка ⌈ m /2⌉ и младшего ⌊ m /2⌋ числа x соответственно. На любой существующей машине это более эффективно, чем вычисления деления или остатка.

В практических реализациях, особенно на машинах с инструкциями сдвига на k и поиска первого нуля , производительность можно дополнительно повысить за счет переключения на битовый массив , как только будет достигнуто m, равное размеру слова (или небольшому кратному ему). Поскольку все операции с одним словом выполняются за постоянное время, это не влияет на асимптотическую производительность, но позволяет избежать большей части хранения указателей и нескольких разыменований указателей, достигая значительной практической экономии времени и пространства с помощью этого трюка.

Оптимизация деревьев vEB заключается в исключении пустых поддеревьев. Это делает деревья vEB довольно компактными, когда они содержат много элементов, поскольку поддеревья не создаются до тех пор, пока к ним не потребуется что-то добавить. Первоначально каждый добавленный элемент создает около log( m ) новых деревьев, содержащих около m /2 указателей вместе. По мере роста дерева все больше и больше поддеревьев используются повторно, особенно более крупные. В полном дереве из M элементов O( M ) используется только пространство . Более того, в отличие от бинарного дерева поиска, большая часть этого пространства используется для хранения данных: даже для миллиардов элементов указатели в полном дереве vEB исчисляются тысячами.

Описанная выше реализация использует указатели и занимает общее пространство O ( M ) = O (2 ^м ) , пропорционально размеру ключевого юниверса. Это можно увидеть следующим образом. Повторение $S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})$.Решение этого вопроса приведет к $S(M)\in (1+{\sqrt {M}})^{\log \log M}+\log \log M\cdot O({\sqrt {M}})$.К счастью, можно также показать по индукции, что S ( M ) = M −2 .

Подобные структуры

Использование пространства O ( M ) для деревьев vEB является огромными накладными расходами, если только не сохраняется большая часть совокупности ключей. Это одна из причин, почему деревья vEB не пользуются популярностью на практике. Это ограничение можно устранить, изменив массив, используемый для хранения дочерних элементов, на другую структуру данных. Одна из возможностей — использовать только фиксированное количество битов на уровень, что приводит к созданию trie . Альтернативно, каждый массив может быть заменен хеш-таблицей , уменьшая пространство до O ( n log log M ) (где n — количество элементов, хранящихся в структуре данных) за счет рандомизации структуры данных.

Попытки x-fast и более сложные попытки y-fast имеют время обновления и запроса, сопоставимое с деревьями vEB, и используют рандомизированные хэш-таблицы для уменьшения используемого пространства. Попытки x-fast используют O ( n log M ), пространство O ( n ) а попытки y-fast используют пространство .

Деревья слияния — это еще один тип древовидной структуры данных, который реализует ассоциативный массив w-битных целых чисел в конечной вселенной. Они используют параллелизм на уровне слов и методы манипуляции битами для достижения времени O (log _w n ) для предшественника/преемника запросов и обновлений , где w — размер слова. Деревья слияния используют пространство O ( n ) и могут быть сделаны динамическими с помощью хеширования или экспоненциальных деревьев.

Реализации

Есть проверенная реализация в Isabelle (помощник по доказательству) . Доказаны как функциональная корректность, так и временные ограничения. эффективный императивный стандартный код ML Можно создать .

См. также

• Целочисленная сортировка
• Дерево танго

Ссылки

Дальнейшее чтение

• Эрик Демейн, Сэм Фингерет, Шравас Рао, Пол Кристиано. Массачусетский технологический институт. 6.851: Расширенные структуры данных (весна 2012 г.). Конспект 11 лекции . 22 марта 2012 г.
• ван Эмде Боас, П .; Каас, Р.; Зийлстра, Э. (1976). «Проектирование и реализация эффективной очереди приоритетов». Теория математических систем . 10 : 99–127. дои : 10.1007/BF01683268 .