Изменения

{{Определение|definition='''Дерево ван Эмде Боаса''' (англ. ''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> и некоторые другие операции, которые присущи всем деревьям поиска.

== Структура ==[[Файл:Дерево_ван_Эмде_Боаса.png|right|570px680px|thumb|Дерево ван Эмде Боаса4-дерево, содержащее в себе 0, 1, 2, 3, 5, 14 и 15. Красным цветом выделены непустые поддеревья]]

Для удобства работы с деревом будем использовать <tex>k</tex>, равные степени двойки.

Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k)</tex>. Тогда при <tex>k = 1-</tex> дерево хранит информацию, содержатся ли в нем <tex>0 </tex> и <tex>1</tex>.

Построим <tex>k</tex>-дерево, при <tex>k \neq 1</tex>. В нем будут хранитсяхраниться:

*максимальный и минимальный элементэлементы, хранящийся хранящиеся в этом дереве (если оно не является пустым), причем дополнительно в самом дереве массиве <tex> chilren </tex> эти элементы хранить не будем.

Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>\mathrm{high(x)}</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>\mathrm{low(x)}</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[\mathrm{high(x)}]</tex> число <tex>\mathrm{low(x)}</tex>.

== Операции ===== empty ===Чтобы определить, пусто ли дерево, будем изначально инициализировать поле <tex>\min</tex> числом, которое не лежит в интервале <tex>[0;2^k)</tex>. Назовем это число <tex>none</tex>. Например, это может быть <tex>-1</tex>, если мы храним в числа в знаковом целочисленном типе, или <tex>2^k</tex>, если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля <tex>\min</tex> с этим числом.<precode> '''boolean''' empty(Tt: '''Tree'''): '''if T''' t.min == ''none'' '''return ''' ''true;'' '''else''' '''return ''' ''false;''</code> === min и max ===Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>\min</tex> или <tex>\max</pretex>в соответствии с запросом. Время выполнения данных операций соответственно <tex>O(1)</tex>.

== min и max ==Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>min</tex> или <tex>max</tex> в соответствии с запросом. Время выполнения данных операций соответственно <tex>O(1)</tex>.=find = find ==

*если число равно полю <tex>\min</tex> или <tex>\max</tex>, то число в дереве есть.*иначе ищем число <tex>\mathrm{low(x)}</tex> в поддереве <tex>children[\mathrm{high(x)}]</tex>.

<precode> '''boolean''' find(Tt: '''Tree''', x: '''int'''): '''if ''' empty(Tt) '''return ''' ''false;'' '''if T''' t.min == x '''or T''' t.max == x '''return ''' ''true;'' '''return ''' find(Tt.children[high(x)], low(x));</precode>

Заметим, что выполняя операцию <tex>\mathrm{find}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>\mathrm{find}</tex> столько раз, какова высота нашего дерева. На каждом уровне мы совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>.

=== insert ===

*если дерево пусто или в нем содержится единственный элемент (<tex>\min</tex> = <tex>\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-дерево, и дальнейшая вставка не требуется.

<precode> '''function''' insert(Tt: '''Tree''', x: '''int'''): '''if ''' empty(Tt) <span style="color:#008000">// проверка на пустоту текущего дерева</span> Tt.min = x; Tt.max = x; '''else''' '''if T''' t.min == Tt.max <span style="color:#008000">// проверка, что в дереве один элемент</span> '''if ''' T.min < x Tt.max = x; '''else''' Tt.min = x; '''else''' '''if T''' t.min > x swap(Tt.min, x); <span style="color:#008000">// релаксация минимума</span> '''if T''' t.max < x swap(Tt.max, x); <span style="color:#008000">// релаксация максимума</span> '''if T''' t.k != 1 '''if ''' empty(Tt.children[high(x)]) insert(Tt.aux, high(x)); <span style="color:#008000">// вставка high(x) во вспомогательно дерево aux</span> insert(Tt.children[high(x)], low(x)); <span style="color:#008000">// вставка low(x) в поддерево children[high(x)]</span></precode>

Нетрудно увидеть, что данная операция работает за время <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 </tex> = <tex> \max </tex> = <tex> 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> из вспомогательного дерева.

<precode> '''function''' remove(Tt: '''Tree''', x: '''int'''): '''if T''' t.min == x '''and T''' t.max == x <span style="color:#008000">// случай, когда в дереве один элемент</span> Tt.min = ''none;'' '''return;''' '''if T''' t.min == x '''if ''' empty(Tt.aux) Tt.min = Tt.max; '''return;''' x = Tmerge(t.aux.min, t.children[Tt.aux.min].min;) Tt.min = x; '''if T''' t.max == x '''if ''' empty(Tt.aux) Tt.max = Tt.min; '''return;''' '''else''' x = Tmerge(t.aux.max, t.children[Tt.aux.max].max;) Tt.max = x; '''if ''' empty(Tt.aux) <span style="color:#008000">// случай, когда элемента x нет в дереве</span> '''return;''' remove(Tt.children[high(x)], low(x)); '''if ''' empty(Tt.children[high(x)]) <span style="color:#008000">// если мы удалили из поддерева последний элемент</span> remove(Tt.aux, high(x)); <span style="color:#008000">// то удаляем информацию, что это поддерево не пусто</span></precode>

Оценка времени работы операции <tex>\mathrm{remove}</tex> такая же, как и у операции <tex>\mathrm{insert}</tex>. На каждом уровне дерева мы совершаем <tex>O(1)</tex> операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>.

=== next и prev ===

*если <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>.

Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. <precode> '''int''' next(Tt: '''Tree''', x: '''int''') '''if ''' empty(Tt) '''or T''' t.max <= x '''return ''' ''none''; <span style="color:#008000">// следующего элемента нет</span> '''if T''' t.min > x '''return T''' t.min; '''if ''' empty(Tt.aux) '''return T''' t.max; <span style="color:#008000">// в дереве не более двух элементов</span> '''else''' '''if ''' '''not ''' empty(Tt.children[high(x)]) '''and T'''t.childen[high(x)].max > low(x) '''return ''' merge(high(x), next(Tt.children[high(x)], low(x))); <span style="color:#008000">// случай, когда следующее число начинается с high(x)</span> '''else ''' <span style="color:#008000">// иначе найдем следующее непустое поддерево</span> '''int''' nextHigh = next(Tt.aux, high(x)); '''if ''' nextHigh == null''none'' '''return T''' t.max; <span style="color:#008000">// если такого нет, вернем максимум</span> '''else''' '''return ''' merge(high(x)nextHigh, Tt.children[nextHigh].min); <span style="color:#008000"> // если есть, вернем минимум найденного поддерева</span></precode>

Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex> \mathrm{prev } </tex> реализуется аналогично.

== Преимущества и недостатки ==

=== Преимущества ===

*cортировка последовательности из <tex> n </tex> чисел. Вставим элементы в дерево, найдем минимум и <tex> n - 1</tex> раз вызовем функцию <tex> \mathrm{next } </tex>. Так как все операции занимают не более <tex> O(\log k)</tex> времени, то итоговая асимптотика алгоритма <tex> O(n \cdot \log k)</tex>, что даже лучше, чем [[Цифровая сортировка|цифровая сортировка]], асимптотика которой <tex> O(n \cdot k)</tex>.

=== Недостатки ===*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает сужает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> O\Theta(2^k) </tex> памяти, что несложно доказывается индукцией, учитывая, что <tex> S(2^k)=(2^{k/2} + 1) \cdot S(2^{k/2}) + O(2^{k/2})</tex>, где <tex> S(2^i) </tex> {{---}} количество памяти, занимаемое деревом, в котором хранятся <tex> i </tex>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются. ==См. также==* [[Поисковые структуры данных]]* [[Дерево поиска, наивная реализация|Дерево поиска]]* [[Алгоритм Дейкстры]]

== Источники информации ==