Изменения

{{Определение|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|680px|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>children</tex>, состоящий из <tex>2^{k/2}</tex> <tex>k/2</tex>-деревьев*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</tex>*максимальный и минимальный элементы, хранящиеся в этом дереве (если оно не является пустым), причем дополнительно в массиве <tex> chilren </tex> эти элементы хранить не будем. Пусть у нас есть множество <tex>mk</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>. Нетрудно увидеть, что высота подобного дерева <tex>\log_{2} k</tex>, так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем. Во вспомогательном дереве <tex>aux</tex> будем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</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>\dots Mmin</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>\mathrm{find}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1]-дерева, то есть выполним операцию <tex>\mathrm{find}</tex> столько раз, какова высота нашего дерева. На каждом уровне мы хотим записать эти данный совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>. === insert ===Операция вставки элемента <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:Boas#008000">// релаксация максимума</span> '''if''' t.k != 1 '''if''' empty(t.jpgchildren[high(x)]) insert(t.jpg|right|380px|thumb|корень дерева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>Taux</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(root1) будут храниться</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени. === remove ===Удаление из дерева также делится на несколько подзадач: *массив детей размером если <tex> \min = \max = x </tex>, значит в дереве один элемент, удалим его и отметим, что дерево пусто.*если <tex> x = \min </tex>, то мы должны найти следующий минимальный элемент в этом дереве, присвоить <tex>sqrt M\min</tex> (Tзначение второго минимального элемента и удалить его из того места, где он хранится.Второй минимум {{---}} это либо <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(Tt.aux) t.max = t.min '''return''' '''else''' x = merge(t.aux.max, Tt.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(Tt.aux, high(x)) <span style="color:#008000">// то удаляем информацию, что это поддерево не пусто</span></code>

Элемент массива из детей с индексом <code> '''int''' next(t: '''Tree''', x: '''int''') '''if''' empty(t) '''or''' t.max <tex>i=\lfloor x '''return''' ''none''; <span style="color:#008000">/M^{1/2}\rfloorследующего элемента нет</texspan> '''if''' t.min > x '''return''' t.min; '''if''' empty(t.aux) '''return''' t.max; <span style="color:#008000"> является также деревом для множества // в дереве не более двух элементов<tex/span> '''else''' '''if''' '''not''' empty(t.children[i sqrthigh(Mx) \dots ]) '''and '''t.childen[high(x)].max > low(i+1x) sqrt '''return''' merge(high(Mx), next(t.children[high(x)- 1], 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></texcode>

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

==Insert=Преимущества ===Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[2-3 дерево|2-3]], [[Splay-дерево|splay]] и [[Декартово дерево|декартовых]] деревьев уже при небольшом количестве элементов. Конечно, из-за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:*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> O(E \cdot \log V)</tex>, где <tex> V </tex> {{---}} количество вершин в графе, а <tex>xE </tex> {{-- эта задача делится на несколько частей-}} количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не <tex> \log V </tex>, а <tex> \log k </tex>, и итоговая асимптотика этого алгоритма снизится до <tex> O(E \cdot \log k)</tex>.

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

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

==Delete==Удаление из дерева T также делится на несколько подзадач*[http:*Если T//en.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее)wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]*Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[Thttp://habrahabr.auxru/post/125499 Дерево ван Эмде Боаса — habrahabr.minru].min.Аналогично для случая x = T.max*Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x. Важно, что 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>