Дерево Ван Эмде Боаса

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

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

• 1 Поддерживаемые операции
• 2 Как это работает
  • 2.1 FindNext
  • 2.2 Вставить
  • 2.3 Удалить
  • 2.4 Реализация Python
  • 2.5 Обсуждение
• 3 См. Также
• 4 Ссылки
  • 4.1 Дополнительная литература

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

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

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

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

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

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

FindNext

Операция FindNext (T, x), которая ищет преемника элемента x в дереве vEB, выполняется следующим образом: Если x

функция FindNext (T, x) ifx < T.min затемвозврат T.min если x ≥ T.max, то / / нет следующего элемента return M i = floor (x / √M) lo = x mod √M если lo < T.children[i].max тогдаreturn ( √M i) + FindNext (T.children [i], lo) j = FindNext (T.aux, i) return (√M j) + T.children [j].min end

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

Insert

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

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

В коде:

function Insert (T, x) if T.min>T.max then // T пусто T.min = T.max = x; return ifx < T.min, затем swap (x, T.min) если x>T.max, то T.max = xi = floor (x / √M) lo = x mod √M Insert (T.children [i], lo) если T.children [i].min == T.children [i].max тогда Insert (T.aux, i) end

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

Удалить

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

1. Если T.min = T.max = x, то x является единственным элементом, хранящимся в tree, и мы устанавливаем T.min = M и T.max = −1, чтобы указать, что дерево пусто.
2. В противном случае, если x == T.min, то мы необходимо найти второе наименьшее значение y в дереве vEB, удалить его из текущего местоположения и установить T.min = y. Второе наименьшее значение 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 и установить T.max = y. Начнем с удаления x, как в предыдущем случае. Тогда значение y равно T.min или T.children [T.aux.max].max, поэтому его можно найти за время O (1).
5. В любом из вышеупомянутые случаи, если мы удаляем последний элемент x или y из любого поддерева T.children [i], мы также удаляем i из T.aux

В коде:

function Delete (T, x) если T.min == T.max == x, то T.min = M T.max = −1 return ifx = = 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, то ifT.aux пуст, тогда T.max = T.min иначе hi = T. aux.max * √M j = T.aux.max T.max = hi + T.children [j].max end

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

Реализация Python

из math import ceil, log2 "" "van Emde Boas Tree - это структура данных, которая дает время запроса O (log (log (u)) для таких операций, как вставка, поиск, удаление, класс преемника и предшественника VEB содержит атрибут min, max, u, w, кластер и сводку изначально min = max = NULL u = размер юниверса (диапазон общих возможных записей) w = длина слова (количество бит в u) w = log2 (u) кластер - это массив структур VEB размером sqrt (u); сводка - это VEB размера sqrt (u), когда размер структуры VEB достигает, мы не сохраняем кластеры, а суммарный вектор min и max достаточно, чтобы сохранить эту структуру. "" "class VEB:" "" Индекс x может быть определен как номер кластера, а позиция внутри кластера, например, позволяет рассмотреть 11 в двоичном формате, он записывается как 1011, поэтому первая половина двоичного strinig дает номер кластера и 2-я половина дает поститон внутри кластера номер кластера = int (10) = 2 позиция внутри кластера = int (11) = 3, поэтому 11 находится во 2-м кластере на 3-м p позиция, где счет начинается с 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 (self, x): # high (x) = x // int (sqrt (u)) return x>>(self.w // 2) def low (self, x): # low (x) = x% int (sqrt (u)) return x (1 << (self.w // 2)) - 1 def index(self, i, j): # return i*int(sqrt(self.u))+j return i << (self.w // 2) | j def __init__(self, u): """ This have been implemented using hash table to reduce the space complexity from O(U) to O(n*log(log(u)) because u can be very large. for example if word size = 64 bits u= 2^64 = 16 million TB which can't be stored practically on ram. where as n*log*log*u can be O(3n) which can be easily stored. I have a different code for array implementation too. """ self.w = ceil(log2(u)) # self.u = 2 ** self.w self.min = self.max = None if self.w>= 1: # когда u == 2 ^ w = 2 min и max достаточно, поэтому мы останавливаем рекурсию self.cluster = {} self.summary = None def member (self, x): "" "Функция для проверки наличия x в дереве или нет. "" "if x == self.min или x == self.max: return True elif self.w == 1: return False else: c = self.high (x) i = self.low (x) если c в self.cluster: вернуть self.cluster [c].member (i) else: return False def insert (self, x): if self.min is None: self.min = x self.max = x return else: if x < self.min: x, self.min = self.min, x c = self.high(x) i = self.low(x) if self.w>1: if c not in self.cluster: self.cluster [c] = VEB (2 ** (self.w // 2)) if self.cluster [c].min Нет: если для self.summary установлено значение Нет: self.summary = VEB (2 ** (self.w // 2)) self.sum mary.insert (c) if c не в self.cluster: self.cluster [c] = VEB (2 ** (self.w // 2)) self.cluster [c].insert (i) if x>self.max: self.max = x def Succesor (self, x): if self.w == 1: if x == 0 и self.max == 1: return 1 else: return None elif self.min не None и x < self.min: return self.min else: c = self.high(x) i = self.low(x) if c in self.cluster: maxlow = self.cluster[c].max else: maxlow = None if maxlow is not None and i < maxlow: offset = self.cluster[c].succesor(i) return self.index(c, offset) else: if self.summary is not None: succ_cluster = self.summary.succesor(self.high(x)) else: succ_cluster = None if succ_cluster is None: return None else: offset = self.cluster[succ_cluster].min return self.index(succ_cluster, offset) def predecessor(self, x): if self.w == 1: if x == 1 and self.min == 0: return 0 else: return None elif self.max is not None and x>self.max: return self.max else: c = self.high (x) i = self.low (x) if c в self.cluster: min_low = self.cluster [c].min else: min_low = Нет, если min_low не равно None и i>min_low: offset = self.cluster [c].predecessor (i) return self.index (c, offset) else: if self.summary is not None: prev_cluster = self.summary.predecessor (c) else: prev_cluster = None, если prev_cluster равен None: если self.min не равен None и x>self.min: return self.min else: return None else: offset = self.cluster [prev_cluster].max return self.index (prev_cluster, offset) def delete (self, x): if self.min is None: return if x < self.min or x>self.max: return if self.min == self.max: self.min = self. max = Нет elif self.w == 1: if x == 0: self.min = 1 else: self.min = 0 self.ma x = self.min else: c = self.high (x) i = self.low (x) if x == self.min: if self.summary: first_cluster = self.summary.min else: first_cluster = None if first_cluster : x = self.index (first_cluster, self.cluster [first_cluster].min) self.min = x, если c в self.cluster: self.cluster [c].delete (i) if self.cluster [c].min равно None: self.summary.delete (c) if x == self.max: summary_max = self.summary.max, если summary_max имеет значение None: self.max = self.min else: self.max = self.index (summary_max, self.cluster [summary_max].max) elif x == self.max: self.max = self.index (c, self.cluster [c].max)

.

Обсуждение

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

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

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

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

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

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

Дополнительная литература