Изменения

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

== Структура ==[[Файл:Boas.jpgДерево_ван_Эмде_Боаса.jpgpng|right|378px680px|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;''</precode>

=== 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>

Заметим, что выполняя операцию <pretex>\mathrm{find(T}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, x) if empty(T) return false; if Tвыходим из нее.min == x or T.max == x return true; return В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>\mathrm{find(T}</tex> столько раз, какова высота нашего дерева.children[highНа каждом уровне мы совершаем <tex>O(x1)], low</tex> операций. Следовательно время работы <tex>O(x\log k));</pretex>.

=== 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-дерево, и дальнейшая вставка не требуется. <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>\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> 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>.**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае. <code> '''int''' next(t: '''Tree''', x: '''int''') '''if''' empty(t) '''or''' t.max <= x '''return''' ''none''; <span style="color:#008000">// следующего элемента нет</span> '''if''' t.min > x '''return''' t.min; '''if''' empty(t.aux) '''return''' t.max; <span style="color:#008000">// в дереве не более двух элементов</span> '''else''' '''if''' '''not''' empty(t.children[high(x)]) '''and '''t.childen[high(x)].max > low(x) '''return''' merge(high(x), next(t.children[high(x)], low(x))); <span style="color:#008000">// случай, когда следующее число начинается с high(x)</span> '''else''' <span style="color:#008000">// иначе найдем следующее непустое поддерево</span> '''int''' nextHigh = next(t.aux, high(x)); '''if''' nextHigh == ''none'' '''return''' t.max; <span style="color:#008000">// если такого нет, вернем максимум</span> '''else''' '''return''' merge(nextHigh, t.children[nextHigh].min); <span style="color:#008000"> // если есть, вернем минимум найденного поддерева</span></code> Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex>\mathrm{prev} </tex> реализуется аналогично.

<pre>insert(T, x) if empty(T) // проверка на пустоту текущего дерева T.min = x; T.max = x; else if T.min Преимущества и недостатки == T.max // проверка, что в дереве один элемент if T.min < x T.max = x; else T.min = x; else if T.min > x swap(T.min, x); // релаксация минимума if T.max < x swap(T.max, x); // релаксация максимума if T.k != 1 if empty(T.children[high(x)]) insert(T.aux, high(x)); // вставка high(x) во вспомогательно дерево aux insert(T.children[high(x)], low(x)); // вставка low(x) в поддерево children[high(x)]</pre>

Нетрудно увидеть=== Преимущества ===Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[2-3 дерево|2-3]], [[Splay-дерево|splay]] и [[Декартово дерево|декартовых]] деревьев уже при небольшом количестве элементов. Конечно, что данная операция работает из-за время <tex>O(\log k)</tex>довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. На каждом уровне Но все же, при большом количестве элементов, эффективность дерева мы выполняем ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:*cортировка последовательности из <tex>O(1)n </tex> операцийчисел. После этого возможны 2 случая: поддерево Вставим элементы в дерево, найдем минимум и <tex>children[high(x)]n - 1</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево раз вызовем функцию <tex>aux\mathrm{next} </tex>, или же поддерево . Так как все операции занимают не пусто, и мы просто спустимся на уровень ниже. Но если поддерево более <tex>children[highO(x\log k)]</tex> пустовремени, то вставка в него будет выполнена за итоговая асимптотика алгоритма <tex>O(1n \cdot \log k)</tex>, так как мы всего лишь обновим поля что даже лучше, чем [[Цифровая сортировка|цифровая сортировка]], асимптотика которой <tex>minO(n \cdot k)</tex> и .*[[Алгоритм Дейкстры|алгоритм Дейкстры]]. Данный алгоритм с использованием [[Двоичная куча|двоичной кучи]] для поиска минимума работает за <tex>maxO(E \cdot \log V)</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом , где <tex>auxV </tex>{{---}} количество вершин в графе, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево а <tex>children[high(x)]E </tex> не пусто{{---}} количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив релаксация и поиск минимума будут занимать уже не <tex>O(1)\log V </tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, а <tex>O(\log k)</tex>. То есть операция вставки займет , и итоговая асимптотика этого алгоритма снизится до <tex>O(E \cdot \log k)</tex> времени.

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

<pre>Delete(T, x) if (T.min == TСм.max также== x) T.min = M T.max = -1 return if (x == T.min) if (T.aux is empty) T.min = T.max return else x = T.children* [[T.aux.minПоисковые структуры данных]].min T.min = x if (x == T.max) if (T.aux is empty) T.max = T.min return else x = T.children* [[T.aux.maxДерево поиска, наивная реализация|Дерево поиска]].max T.max = x if (T.aux is empty) return i = floor(x/sqrt(M)) Delete(T.children* [[iАлгоритм Дейкстры], x%sqrt(M)) if (T.children[i] is empty) Delete(T.aux, i)(с)wikipedia.org</pre>== next и prev ==

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