Изменения

Перейти к: навигация, поиск

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

20 байт добавлено, 00:32, 30 мая 2015
м
Нет описания правки
'''Дерево ван Эмде Боаса'''(англ. ''Van Emde Boas tree, vEB tree'') {{---}} структура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^k)</tex> и осуществлять над ними все соответствующие дереву поиска операции.
Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>\mathrm{find}</tex>, <tex>\mathrm{insert}</tex>, <tex>\mathrm{remove}</tex>, <tex>\mathrm{next}</tex>, <tex>\mathrm{prev}</tex>, <tex>\mathrm{\min}</tex>, <tex>\mathrm{max}</tex> и некоторые другие операции, которые присущи всем деревьям поиска.
Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log k)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.
== Операции ==
=== empty ===
Чтобы определить, пусто ли дерево, будем изначально инициализировать поле <tex>\min</tex> числом, которое не лежит в интервале <tex>[0;2^k)</tex>. Назовем это число <tex>none</tex>. Например, это может быть <tex>-1</tex>, если мы храним в числа в знаковом целочисленном типе, или <tex>2^k</tex>, если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля <tex>\min</tex> с этим числом.
<code>
'''boolean''' empty(t: '''Tree'''): '''if''' t.min == ''none'' '''return''' true;
'''else'''
'''return''' false;
</code>
=== min и max ===
Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>\min</tex> или <tex>\max</tex> в соответствии с запросом. Время выполнения данных операций соответственно <tex>O(1)</tex>.
=== find ===
Алгоритм поиска сам напрашивается из выше описанной структуры:
*если дерево пусто, то число не содержится в нашей структуре.
*если число равно полю <tex>\min</tex> или <tex>\max</tex>, то число в дереве есть.
*иначе ищем число <tex>\mathrm{low(x)}</tex> в поддереве <tex>children[\mathrm{high(x)}]</tex>.
<code>
'''boolean''' find(t: '''Tree''', x: '''int'''):
'''if''' empty(t)
'''return''' false;
'''if''' t.min == x '''or''' t.max == x
'''return''' true; '''return''' find(t.children[high(x)], low(x));
</code>
Операция вставки элемента <tex>x</tex> состоит из нескольких частей:
*если дерево пусто или в нем содержится единственный элемент (<tex> \min = \max </tex>), то присвоим полям <tex>\min</tex> и <tex>\max</tex> соответствующие значения. Делать что-то еще бессмысленно, так как информация записанная в <tex>\min</tex> и <tex>\max</tex> полностью описывает состояние текущего дерева и удовлетворяет структуре нашего дерева.
*иначе:
**если элемент <tex>x</tex> больше <tex>\max</tex> или меньше <tex>\min</tex> текущего дерева, то обновим соответствующее значение минимума или максимума, а старый минимум или максимум добавим в дерево.
**вставим во вспомогательное дерево <tex>aux</tex> число <tex>\mathrm{high(x)}</tex>, если соответствующее поддерево <tex>children[\mathrm{high(x)}]</tex> до этого было пусто.
**вставим число <tex>\mathrm{low(x)}</tex> в поддерево <tex>children[\mathrm{high(x)}]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется.
<code>
'''function''' insert(t: '''Tree''', x: '''int'''):
'''if''' empty(t) <span style="color:#008000">// проверка на пустоту текущего дерева</span>
t.min = x; t.max = x;
'''else'''
'''if''' t.min == t.max <span style="color:#008000">// проверка, что в дереве один элемент</span>
'''if''' T.min < x
t.max = x;
'''else'''
t.min = x;
'''else'''
'''if''' t.min > x
swap(t.min, x); <span style="color:#008000">// релаксация минимума</span>
'''if''' t.max < x
swap(t.max, x); <span style="color:#008000">// релаксация максимума</span>
'''if''' t.k != 1
'''if''' empty(t.children[high(x)])
insert(t.aux, high(x)); <span style="color:#008000">// вставка high(x) во вспомогательно дерево aux</span> insert(t.children[high(x)], low(x)); <span style="color:#008000">// вставка low(x) в поддерево children[high(x)]</span>
</code>
Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[\mathrm{high(x)}]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[\mathrm{high(x)}]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>\min</tex> и <tex>\max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[\mathrm{high(x)}]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.
=== remove ===
Удаление из дерева также делится на несколько подзадач:
*если <tex> \min = \max = x </tex>, значит в дереве один элемент, удалим его и отметим, что дерево пусто.*если <tex> x = \min </tex>, то мы должны найти следующий минимальный элемент в этом дереве, присвоить <tex>\min</tex> значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум {{---}} это либо <tex> \max </tex>, либо <tex> children[aux.min].min </tex> (для случая <tex> x = \max </tex> действуем аналогично).*если же <tex> x \neq \min </tex> и <tex> x \neq \max </tex>, то мы должны удалить <tex>\mathrm{low(x)}</tex> из поддерева <tex>children[\mathrm{high(x)}]</tex>.
Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. Также нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>\mathrm{high(x)}</tex> из вспомогательного дерева.
<code>
'''function''' remove(t: '''Tree''', x: '''int'''):
'''if''' t.min == x '''and''' t.max == x <span style="color:#008000">// случай, когда в дереве один элемент</span>
t.min = ''none;'' '''return''';
'''if''' t.min == x
'''if''' empty(t.aux)
t.min = t.max; '''return'''; x = merge(t.aux.min, t.children[t.aux.min].min); t.min = x;
'''if''' t.max == x
'''if''' empty(t.aux)
t.max = t.min; '''return''';
'''else'''
x = merge(t.aux.max, t.children[t.aux.max].max); t.max = x;
'''if''' empty(t.aux) <span style="color:#008000">// случай, когда элемента x нет в дереве</span>
'''return'''; remove(t.children[high(x)], low(x));
'''if''' empty(t.children[high(x)]) <span style="color:#008000">// если мы удалили из поддерева последний элемент</span>
remove(t.aux, high(x)); <span style="color:#008000">// то удаляем информацию, что это поддерево не пусто</span>
</code>
Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:
*если дерево пусто, или максимум этого дерева не превосходит <tex> x </tex>, то следующего элемента в этом дереве не существует.
*если <tex> x </tex> меньше поля <tex> \min </tex>, то искомый элемент и есть <tex> \min </tex>.*если дерево содержит не более двух элементов, и <tex> x < \max </tex>, то искомый элемент <tex> \max </tex>.
*если же в дереве более двух элементов, то:
**если в дереве есть еще числа, большие <tex> x </tex>, и чьи старшие биты равны <tex>\mathrm{high(x)} </tex>, то продолжим поиск в поддереве <tex> children[\mathrm{high(x)}] </tex>, где будем искать число, следующее после <tex>\mathrm{low(x)} </tex>.
'''int''' next(t: '''Tree''', x: '''int''')
'''if''' empty(t) '''or''' t.max <= x
'''return''' -1''none''; <span style="color:#008000">// следующего элемента нет</span>
'''if''' t.min > x
'''return''' t.min;
251
правка

Навигация