1632
правки
Изменения
м
{{Определение|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> и некоторые другие операции, которые присущи всем деревьям поиска.
*Если дерево пусто<code> '''int''' next(t: '''Tree''', то меняем значения минимума и максимума на x;: '''int''')*Если '''if''' empty(t) '''or''' t.max <= x '''return''' ''none''; <Tspan style="color:#008000">// следующего элемента нет</span> '''if''' t.min тогда мы кладем T> x '''return''' t.min в поддерево i соответствующее T; '''if''' empty(t.min и ставим Taux) '''return''' t.min max; <span style= "color:#008000">// в дереве не более двух элементов</span> '''else''' '''if''' '''not''' empty(t.children[high(x)]) '''and '''t. Если поддеревоchilden[ihigh(x)] до этого было пусто то мы также добавляем i в вспомогательное дерево.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">T// иначе найдем следующее непустое поддерево</span> '''int''' nextHigh = next(t.aux, high(x)); '''if''' nextHigh == ''none'' '''return''' t.max; <span style="color:#008000">// если такого нет, вернем максимум</span> '''else''' '''return''' merge(nextHigh, t.*Если Tchildren[nextHigh].min); <span style="color:#008000"> // если есть, вернем минимум найденного поддерева< x /span>< T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево./code>
(с)wikipedia.org</pre>== Преимущества и недостатки ==
<pre>Delete(T, x) if (T.min == T.max = Недостатки === x) T*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно сужает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.min = M T*другим серьезным недостатком является количество занимаемой памяти.max = Дерево, хранящее <tex> k </tex>-1 return if битные числа, занимает <tex> \Theta(x == T.min2^k) if </tex> памяти, что несложно доказывается индукцией, учитывая, что <tex> S(T.aux is empty2^k) T.min = T.max return else x = T.children[T.aux.min].min T.min = x if (x == T.max2^{k/2} + 1) if \cdot S(T.aux is empty2^{k/2}) T.max = T.min return else x = T.children[T.aux.max].max T.max = x if + O(T.aux is empty2^{k/2}) return i = floor(x</sqrt(M)) Delete(T.children[i]tex>, x%sqrtгде <tex> S(M)) if (T.children[2^i] is empty) Delete(T.aux</tex> {{---}} количество памяти, занимаемое деревом, в котором хранятся <tex> i)(с)wikipedia.org</pretex>== min и max ==-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
rollbackEdits.php mass rollback
Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log k)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</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>children</tex>, состоящий из <tex>2^{k/2}</tex> <tex>k/2</tex>-деревьев
*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</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>.
Нетрудно увидеть, что высота подобного дерева <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''Рассмотрим две опeрации '''return''' ''true'' '''else''' '''return''' ''false''</code> === min и max ===InsertТак как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <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>.Delete<code> '''boolean''' find(Tt: '''Tree''', x: '''int'''): '''if''' empty(t) '''return''' ''false'' '''if''' t.min == find 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:#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>.**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.
Время работы, как и всех предыдущих функций, оценивается так же, и равно <pretex>InsertO(T, x\log k) if (T.min </tex> 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 tex> T.max) T.max = x; return if (x \mathrm{prev} < T.min) swap(x, T.min) if (x /tex> 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)
== remove = Преимущества ===Удаление Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[2-3 дерево|2-3]], [[Splay-дерево|splay]] и [[Декартово дерево|декартовых]] деревьев уже при небольшом количестве элементов. Конечно, из -за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева T также делится ван Эмде Боаса проявляется и на несколько подзадачпрактике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:*Если Tcортировка последовательности из <tex> n </tex> чисел.min = T.max = x, значит Вставим элементы в дереве один элементдерево, мы его удалим найдем минимум и <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>.*Если x = T[[Алгоритм Дейкстры|алгоритм Дейкстры]].minДанный алгоритм с использованием [[Двоичная куча|двоичной кучи]] для поиска минимума работает за <tex> O(E \cdot \log V)</tex>,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум <tex> V </tex> {{--- это либо T.max}} количество вершин в графе, либо T.children[T.aux.min].minа <tex> E </tex> {{---}} количество ребер между ними.Аналогично для случая x = T.max*Если же x = T.min и x = T.maxвместо кучи использовать дерево ван Эмде Боаса, то мы должны удалить x из поддерева i отвечающего x. Важно, что Delete реализован рекурсивно от дерева в котором идет удаления.Так же нельзя забыватьрелаксация и поиск минимума будут занимать уже не <tex> \log V </tex>, что если мы удаляем последнее вхождение xа <tex> \log k </tex>, то мы должны удалить i из вспомогательного дереваи итоговая асимптотика этого алгоритма снизится до <tex> O(E \cdot \log k)</tex>.
== next и prev См. также==* [[Поисковые структуры данных]]* [[Дерево поиска, наивная реализация|Дерево поиска]]* [[Алгоритм Дейкстры]]
== Источники информации ==
*[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
[[Категория: Структуры данных]]