Викиконспекты - Вклад участника [ru]

Дерево ван Эмде Боаса

2012-04-07T20:52:51Z

84.242.228.169: /* Операции */

{{Определение
|definition=
'''Дерево ван Эмде Боаса''' {{---}} структура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^k)</tex> и осуществлять над ними все соответствующие дереву поиска операции.
}}
Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>find</tex>, <tex>insert</tex>, <tex>remove</tex>, <tex>next</tex>, <tex>prev</tex>, <tex>min</tex>, <tex>max</tex> и некоторые другие операции, которые присущи всем деревьям поиска.

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

= Структура =
[[Файл:Boas.jpg.jpg|right|378px|thumb|корень дерева]]

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

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

Построим <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>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>high(x)</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>low(x)</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[high(x)]</tex> число <tex>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> с этим числом.
<pre>
empty(T)
if T.min == none
return true;
else
return false;
</pre>

== min и max ==
Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>min</tex> или <tex>max</tex> в соответствии с запросом. Время выполнения данных операций соответственно <tex>O(1)</tex>.
== find ==
Алгоритм поиска сам напрашивается из выше описанной структуры:
*если дерево пусто, то число не содержится в нашей структуре
*если число равно полю <tex>min</tex>, то число в дереве есть
*иначе ищем число <tex>low(x)</tex> в поддереве <tex>children[high(x)]</tex>

<pre>
find(T, x)
if empty(T)
return false;
if T.min == x
return true;
return find(T.children[high(x)], low(x));
</pre>

== insert ==
Операция вставки элемента <tex>x</tex> состоит из нескольких частей:

*если дерево пусто, то присвоим полям <tex>min</tex> и <tex>max</tex> значение <tex>x</tex>. Делать что-то еще бессмысленно, так как информация записанная в <tex>min</tex> и <tex>max</tex> полностью описывает состояние текущего дерева.
*иначе:
**обновим поля <tex>min</tex> и <tex>max</tex> текущего дерева, если это требуется
**вставим во вспомогательное дерево <tex>aux</tex> число <tex>high(x)</tex>, если соответствующее поддерево <tex>children[high(x)]</tex> до этого было пусто
**вставим число <tex>low(x)</tex> в поддерево <tex>children[high(x)]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется

<pre>
insert(T, x)
if empty(T) // проверка на пустоту текущего дерева
T.min = x;
T.max = x;
else
if T.min > x
T.min = x; // релаксация минимума
if T.max < x
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>

Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[high(x)]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[high(x)]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>min</tex> и <tex>max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[high(x)]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.

== remove ==
Удаление из дерева T также делится на несколько подзадач:
*Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее).
*Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].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>
== next и prev ==

= Источники =

*[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]
*[http://habrahabr.ru/post/125499 Дерево ван Эмде Боаса — habrahabr.ru]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]

Дерево ван Эмде Боаса

2012-04-07T16:50:11Z

84.242.228.169: /* Структура */