Изменения

==Структура==Пусть есть множество <tex>m[0 '''Дерево ван Эмде Боаса''' (англ.. M''Van Emde Boas tree, vEB tree'') {{---1]</tex> мы хотим записать эти данный в дерево.}} структура данных, представляющая собой [[Файл:Boas.jpg.jpgДерево поиска, наивная реализация|right|380px|thumb|корень деревадерево поиска]]Будем называть наше дерево , позволяющее хранить целые неотрицательные числа в интервале <tex>T</tex>.В корне(root[0;2^k) будут храниться: *массив детей размером <tex>sqrt{M}</tex> (T.children[]) *значение текущего минимума и максимума в дерево (T.min, Tосуществлять над ними все соответствующие дереву поиска операции.max)*вспомогательный массив (T.aux)

Элемент массива из детей с индексом <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для множества <tex>= Структура ==[[i<tex>sqrt{M^Файл:Дерево_ван_Эмде_Боаса.png|right|680px|thumb|4-дерево, содержащее в себе 0, 1/, 2}</tex> , 3, 5, 14 и 15.. (i+1)<tex>sqrt{M^1/2}</tex> - 1Красным цветом выделены непустые поддеревья]]</tex>

В вспомогательном дереве хранится информация о том, какие клетки уже заняты. То есть значение <tex>i</tex> хранится в вспомогательном дереве только если занят элемент Для удобства работы с индексом деревом будем использовать <tex>ik </tex> в массиве детей, равные степени двойки.

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

==Insert==Построим <tex>k</tex>-дерево, при <tex>k \neq 1</tex>. В нем будут храниться:*массив <tex>children</tex>, состоящий из <tex>2^{k/2}</tex> <tex>k/2</tex>-деревьевОперация добавления элемента *вспомогательное <tex>xk/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<T/tex> младшим битам.min тогда мы кладем T.min Тогда информация, хранится ли в поддерево i соответствующее T.min и ставим T.min = данном дереве число <tex>x. Если поддерево</tex>, эквивалентна информации, содержится ли в дереве <tex>children[i\mathrm{high(x)}] до этого было пусто то мы также добавляем i в вспомогательное дерево.Аналогично если x</tex>T.max.*Если T.minчисло < tex>\mathrm{low(x )}< T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево/tex>.

Нетрудно увидеть, что высота подобного дерева <pretex>Insert(T, x) if (T.min > T.max) /\log_{2} k</ 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 < T.min) swap(x, T.min) if (x > T.max) swap(xтак как каждый следующий уровень дерева содержит числа, T.max) i = x/sqrt(M) Insert(T.children[i]количество битов в которых в 2 раза меньше, x % sqrt(M)) if (T.children[i]чем в предыдущем.min = T.children[i].max) Insert(T.aux, i)

(с)wikipedia.orgВо вспомогательном дереве <tex>aux</tex> будем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</pretex>не пусто.

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

=== min и max ===Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>\min</tex> или <tex>\max</tex> в соответствии с запросом. Время выполнения данных операций соответственно <pretex>O(1)</tex>.Delete=== find ===Алгоритм поиска сам напрашивается из выше описанной структуры:*если дерево пусто, то число не содержится в нашей структуре.*если число равно полю <tex>\min</tex> или <tex>\max</tex>, то число в дереве есть.*иначе ищем число <tex>\mathrm{low(Tx)}</tex> в поддереве <tex>children[\mathrm{high(x)}]</tex>. <code> '''boolean''' find(t: '''Tree''', x: '''int'''): '''if ''' empty(Tt) '''return''' ''false'' '''if''' t.min == Tx '''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> Tt.min = Mx 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> значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум {{-1--}} это либо <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> return '''function''' remove(t: '''Tree''', x: '''int'''): '''if (''' t.min == x '''and''' t.max == x <span style="color:#008000">// случай, когда в дереве один элемент</span> t.min = T''none'' '''return''' '''if''' t.min)== x '''if ''' empty(Tt.aux is empty) Tt.min = Tt.max '''return''' else x = Tmerge(t.aux.min, t.children[Tt.aux.min].min) T t.min = x '''if (x ''' t.max == T.max)x '''if ''' empty(Tt.aux is empty) Tt.max = Tt.min '''return''' '''else''' x = Tmerge(t.aux.max, t.children[Tt.aux.max].max) Tt.max = x '''if ''' empty(Tt.aux is empty) <span style="color:#008000">// случай, когда элемента x нет в дереве</span> '''return''' remove(t.children[high(x)], low(x)) i '''if''' empty(t.children[high(x)]) <span style= floor"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)</sqrttex> операций и переходим к удалению элементов максимум в двух деревьях(Mв одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>. === next и prev ===Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев: Delete*если дерево пусто, или максимум этого дерева не превосходит <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(T.x)} </tex>, то продолжим поиск в поддереве <tex> children[i\mathrm{high(x)}]</tex>, где будем искать число, следующее после <tex>\mathrm{low(x%sqrt)} </tex>.**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае. <code> '''int''' next(t: '''Tree''', x: '''int''') '''if''' empty(Mt)'''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(Tt.children[high(x)]) '''and '''t.childen[high(x)].max > low(x) '''return''' merge(high(x), next(t.children[ihigh(x)] is empty, low(x))); <span style="color:#008000">// случай, когда следующее число начинается с high(x) </span> Delete'''else''' <span style="color:#008000">// иначе найдем следующее непустое поддерево</span> '''int''' nextHigh = next(Tt.aux, ihigh(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> реализуется аналогично. == Преимущества и недостатки == === Преимущества ===Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[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> E </tex> {{---}} количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не <tex> \log V </tex>, а <tex> \log k </tex>, и итоговая асимптотика этого алгоритма снизится до <tex> O(E \cdot \log k)</tex>. === Недостатки ===*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно сужает область ее применения, по сравнению сдругими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> \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>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются. ==См. также==* [[Поисковые структуры данных]]* [[Дерево поиска, наивная реализация|Дерево поиска]]* [[Алгоритм Дейкстры]] == Источники информации == *[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]<*[http://habrahabr.ru/post/pre>125499 Дерево ван Эмде Боаса — habrahabr.ru] [[Категория: Дискретная математика и алгоритмы]][[Категория: Деревья поиска]][[Категория: Структуры данных]]