Дерево Ван Эмде Боаса - Van Emde Boas tree

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

А дерево ван Эмде Боас (Голландское произношение: [vɑn 'ɛmdə' boːɑs]), также известный как vEB дерево или же приоритетная очередь van Emde Boas, это древовидная структура данных который реализует ассоциативный массив с м-битовые целочисленные ключи. Выполняет все операции в О (бревном) время или что то же самое в О(журнал журналаM) время, где M = 2^м - максимальное количество элементов, которое можно сохранить в дереве. В M не следует путать с фактическим количеством элементов, хранящихся в дереве, по которому часто измеряется производительность других древовидных структур данных. Дерево vEB имеет хорошую эффективность использования пространства, когда оно содержит много элементов, как обсуждается ниже. Его изобрела команда во главе с нидерландский язык специалист в области информатики Питер ван Эмде Боас в 1975 г.^[1]

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

VEB поддерживает операции упорядоченный ассоциативный массив, который включает в себя обычные операции с ассоциативными массивами, а также еще два порядок операции, Найти следующий и FindPrevious:^[2]

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

Дерево vEB также поддерживает операции Минимум и Максимум, которые возвращают минимальный и максимальный элементы, хранящиеся в дереве соответственно.^[3] Они оба работают О(1) time, поскольку минимальный и максимальный элемент хранятся как атрибуты в каждом дереве.

Как это устроено

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

Пусть для простоты бревно₂ м = k для некоторого целого числа k. Определять M = 2^м. ВЭБ-дерево Т над вселенной {0, ..., M−1} имеет корневой узел, в котором хранится массив T. дети длины √M. T.children [i] указатель на дерево vEB, отвечающее за значения {я√M, ..., (я+1)√M−1}. Кроме того, Т хранит два значения T.min и T.max а также вспомогательное дерево vEB T.aux.

Данные хранятся в дереве vEB следующим образом: наименьшее значение в настоящее время в дереве хранится в T.min и наибольшее значение хранится в T.max. Обратите внимание, что T.min больше нигде в дереве vEB не хранится, а T.max является. Если Т пусто, то мы используем соглашение, что T.max = −1 и T.min = M. Любое другое значение Икс хранится в поддереве T.children [i] куда я = ⌊Икс/√M⌋. Вспомогательное дерево T.aux отслеживает, какие дочерние элементы не пустые, поэтому T.aux содержит значение j если и только если T.children [j] не пусто.

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

Операция НайтиСледующий (Т, х) который ищет преемника элемента Икс в дереве vEB происходит следующим образом: Если Икс то поиск завершен, и ответ T.min. Если x≥T.max тогда следующий элемент не существует, верните M. В противном случае пусть я = Икс/√M. Если x то искомое значение содержится в T.children [i] поэтому поиск выполняется рекурсивно в T.children [i]. В противном случае ищем значение я в T.aux. Это дает нам индекс j первого поддерева, содержащего элемент больше, чем Икс. Затем алгоритм возвращает T.children [j] .min. Элемент, обнаруженный на уровне дочерних элементов, должен состоять из старших битов, чтобы сформировать завершенный следующий элемент.

функция НайтиСледующий (Т, х) если х тогда        возвращаться T.min если x ≥ Tмакс. тогда // нет следующего элемента        возвращаться M i = этаж (x /√M) lo = x mod √M        если lo тогда        возвращаться (√M i) + FindNext (T.children [i], lo) j = FindNext (T.aux, i) возвращаться (√M j) + T.children [j] .minконец

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

Вставлять

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

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

В коде:

функция Вставить (T, x) если T.min> T.max тогда // Т пусто        T.min = T.max = x; возвращаться    если х тогда        swap (x, T.min) если x> T.max тогда        T.max = x i = этаж (x / √M) lo = x mod √M    Вставить (T.children [i], lo) если T.children [i] .min == T.children [i] .max тогда        Вставить (T.aux, i)конец

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

Удалить

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

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

В коде:

функция Удалить (T, x) если T.min == T.max == x тогда        T.min = M T.max = −1 возвращаться    если x == T.min тогда        hi = T.aux.min * √M        j = T.aux.min T.min = x = hi + T.children [j] .min i = floor (x / √M) lo = x mod √M    Удалить (T.children [i], lo) если T.children [i] пусто тогда        Удалить (T.aux, i) если x == T.max тогда        если T.aux пуст тогда            T.max = T.min еще            hi = T.aux.max * √M            j = T.aux.max T.max = hi + T.children [j] .maxконец

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

Реализация Python

из математика импорт потолок, log2"""van Emde Boas Tree - это структура данных, которая дает O (log (log (u))время запроса для таких операций, как вставка, поиск, удаление, преемник и предшественникКласс VEB содержит атрибутmin, max, u, w, кластер и сводкаизначально min = max = NULLu = размер вселенной (диапазон всех возможных записей)w = длина слова (количество бит в u)ш = log2 (и)cluster - это массив структур VEB размером sqrt (u)сводка - это ВЭБ размером sqrt (u)при достижении размера структуры ВЭБ мы не сохраняем кластеры и суммарный векторmin и max достаточно для хранения этой структуры."""учебный класс ВЭБ:    "" "Индекс x можно определить как    номер кластера и положение внутри кластера    например, давайте рассмотрим 11    в двоичном формате записывается как 1011    поэтому первая половина двоичного strinig дает номер кластера    а вторая половина дает поститон внутри кластера    номер кластера = int (10) = 2    позиция внутри кластера = int (11) = 3    поэтому 11 находится во 2-м кластере на 3-й позиции    где отсчет начинается с 0 позиции    0,1,2,3|4,5,6,7|8,9,10,11|12,13,14,15                           ^    здесь мы используем 'c' для обозначения номера кластера    и 'i' для обозначения индекса внутри кластера    поэтому x можно представить как     где x = c * sqrt (u) + i    """    def высоко(себя, Икс):        # high (x) = x // int (sqrt (u))        возвращаться Икс >> (себя.ш // 2)    def низкий(себя, Икс):        # low (x) = x% int (sqrt (u))        возвращаться Икс & (1 << (себя.ш // 2)) - 1    def индекс(себя, я, j):        # вернуть i * int (sqrt (self.u)) + j        возвращаться я << (себя.ш // 2) | j    def __в этом__(себя, ты):        """        Это было реализовано с использованием хеш-таблицы        чтобы уменьшить сложность пространства с O (U) до O (n * log (log (u))        потому что ты может быть очень большим. например, если размер слова = 64 бита        u = 2 ^ 64 = 16 миллионов ТБ, которые практически невозможно хранить в оперативной памяти.        где как n * log * log * u может быть O (3n), который можно легко сохранить.        У меня тоже есть другой код для реализации массива.        """        себя.ш = потолок(log2(ты))        # self.u = 2 ** self.w        себя.мин = себя.Максимум = Никто        если себя.ш >= 1:  # когда u == 2 ^ w = 2 min и max достаточно, поэтому мы останавливаем рекурсию            себя.кластер = {}            себя.резюме = Никто    def член(себя, Икс):        "" "Функция проверки, присутствует ли x в дереве или нет." ""        если Икс == себя.мин или же Икс == себя.Максимум:            возвращаться Истинный        Элиф себя.ш == 1:            возвращаться Ложь        еще:            c = себя.высоко(Икс)            я = себя.низкий(Икс)            если c в себя.кластер:                возвращаться себя.кластер[c].член(я)            еще:                возвращаться Ложь    def вставлять(себя, Икс):        если себя.мин является Никто:            себя.мин = Икс            себя.Максимум = Икс            возвращаться        еще:            если Икс < себя.мин:                Икс, себя.мин = себя.мин, Икс            c = себя.высоко(Икс)            я = себя.низкий(Икс)            если себя.ш > 1:                если c нет в себя.кластер:                    себя.кластер[c] = ВЭБ(2 ** (себя.ш // 2))                если себя.кластер[c].мин является Никто:                    если себя.резюме является Никто:                        себя.резюме = ВЭБ(2 ** (себя.ш // 2))                    себя.резюме.вставлять(c)                если c нет в себя.кластер:                    себя.кластер[c] = ВЭБ(2 ** (себя.ш // 2))                себя.кластер[c].вставлять(я)            если Икс > себя.Максимум:                себя.Максимум = Икс    def преемник(себя, Икс):        если себя.ш == 1:            если Икс == 0 и себя.Максимум == 1:                возвращаться 1            еще:                возвращаться Никто        Элиф себя.мин является нет Никто и Икс < себя.мин:            возвращаться себя.мин        еще:            c = себя.высоко(Икс)            я = себя.низкий(Икс)            если c в себя.кластер:                Макслоу = себя.кластер[c].Максимум            еще:                Макслоу = Никто            если Макслоу является нет Никто и я < Макслоу:                компенсировать = себя.кластер[c].преемник(я)                возвращаться себя.индекс(c, компенсировать)            еще:                если себя.резюме является нет Никто:                    succ_cluster = себя.резюме.преемник(себя.высоко(Икс))                еще:                    succ_cluster = Никто                если succ_cluster является Никто:                    возвращаться Никто                еще:                    компенсировать = себя.кластер[succ_cluster].мин                    возвращаться себя.индекс(succ_cluster, компенсировать)    def предшественник(себя, Икс):        если себя.ш == 1:            если Икс == 1 и себя.мин == 0:                возвращаться 0            еще:                возвращаться Никто        Элиф себя.Максимум является нет Никто и Икс > себя.Максимум:            возвращаться себя.Максимум        еще:            c = себя.высоко(Икс)            я = себя.низкий(Икс)            если c в себя.кластер:                min_low = себя.кластер[c].мин            еще:                min_low = Никто            если min_low является нет Никто и я > min_low:                компенсировать = себя.кластер[c].предшественник(я)                возвращаться себя.индекс(c, компенсировать)            еще:                если себя.резюме является нет Никто:                    prev_cluster = себя.резюме.предшественник(c)                еще:                    prev_cluster = Никто                если prev_cluster является Никто:                    если себя.мин является нет Никто и Икс > себя.мин:                        возвращаться себя.мин                    еще:                        возвращаться Никто                еще:                    компенсировать = себя.кластер[prev_cluster].Максимум                    возвращаться себя.индекс(prev_cluster, компенсировать)    def Удалить(себя, Икс):        если себя.мин является Никто:            возвращаться        если Икс < себя.мин или же Икс > себя.Максимум:            возвращаться        если себя.мин == себя.Максимум:            себя.мин = себя.Максимум = Никто        Элиф себя.ш == 1:            если Икс == 0:                себя.мин = 1            еще:                себя.мин = 0            себя.Максимум = себя.мин        еще:            c = себя.высоко(Икс)            я = себя.низкий(Икс)            если Икс == себя.мин:                если себя.резюме:                    first_cluster = себя.резюме.мин                еще:                    first_cluster = Никто                если first_cluster:                    Икс = себя.индекс(first_cluster, себя.кластер[first_cluster].мин)                    себя.мин = Икс            если c в себя.кластер:                себя.кластер[c].Удалить(я)                если себя.кластер[c].мин является Никто:                    себя.резюме.Удалить(c)                если Икс == себя.Максимум:                    summary_max = себя.резюме.Максимум                    если summary_max является Никто:                        себя.Максимум = себя.мин                    еще:                        себя.Максимум = себя.индекс(summary_max, себя.кластер[summary_max].Максимум)            Элиф Икс == себя.Максимум:                себя.Максимум = себя.индекс(c, себя.кластер[c].Максимум)

Обсуждение

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

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

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

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

Однако для небольших деревьев накладные расходы, связанные с деревьями vEB, огромны: порядка ${\displaystyle {\sqrt {M}}}$. Это одна из причин, по которой они не пользуются популярностью на практике. Один из способов устранения этого ограничения - использовать только фиксированное количество бит на уровень, что приводит к три. В качестве альтернативы каждую таблицу можно заменить хеш-таблица, уменьшая пространство до О(п бревно M) (куда п - количество элементов, хранящихся в структуре данных) за счет рандомизации структуры данных. Другие конструкции, в том числе y-fast пытается и x-fast пытается были предложены, которые имеют сопоставимое время обновления и запроса, а также используют рандомизированные хэш-таблицы, чтобы уменьшить пространство до О(п) или же О(п бревно M).

Смотрите также

• Целочисленная сортировка
• Проблема предшественника
• Дерево слияния
• Танго дерево
• X-fast trie
• Y-fast trie

Рекомендации

1. Питер ван Эмде Боас: Сохранение порядка в лесу менее чем за логарифмическое время (Материалы 16-го ежегодного симпозиума по основам компьютерных наук 10: 75-84, 1975)
2. Гудмунд Сковбьерг Франдсен: Динамические алгоритмы: Курс по деревьям Ван Эмде Боаса (PDF) (Орхусский университет, Кафедра компьютерных наук)
3. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Третье издание. MIT Press, 2009. ISBN  978-0-262-53305-8. Глава 20: Дерево ван Эмде Боаса, стр. 531–560.
4. Рекс, А. «Определение пространственной сложности деревьев Ван Эмде Боаса». Получено 2011-05-27.

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

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