Дерево ван Эмде Боаса
Дерево ван Эмде Боаса — структура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале и осуществлять над ними все соответствующие дереву поиска операции.
Проще говоря, данная структура позволяет хранить -битные числа и производить над ними операции , , , , , , и некоторые другие операции, которые присущи всем деревьям поиска.
Особенностью этой структуры является то, что все операции выполняются за , что асимптотически лучше, чем в большинстве других деревьев поиска, где — количество элементов в дереве.
Структура
Для удобства работы с деревом будем использовать , равные степени двойки.
Как уже было сказано выше, -дерево хранит числа в интервале . Тогда 1-дерево хранит информацию, содержатся ли в нем 0 и 1.
Построим -дерево, при . В нем будут хранится:
- массив , состоящий из -деревьев
- вспомогательное -дерево, которое назовем
- максимальный и минимальный элемент, хранящийся в этом дереве (если оно не является пустым), причем дополнительно в самом дереве эти элементы хранить не будем.
Пусть у нас есть -битное число . Разобьем это число таким образом, что — число, соответствующее старшим битам числа , а соответствует младшим битам. Тогда информация, хранится ли в данном дереве число , эквивалентна информации, содержится ли в дереве число .
Нетрудно увидеть, что высота подобного дерева , так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.
Во вспомогательном дереве будем хранить все такие числа , что дерево не пусто.
Операции
empty
Чтобы определить, пусто ли дерево, будем изначально инициализировать поле числом, которое не лежит в интервале . Назовем это число . Например, это может быть , если мы храним в числа в знаковом целочисленном типе, или , если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля с этим числом.
empty(T)
if T.min == none
return true;
else
return false;
min и max
Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля или в соответствии с запросом. Время выполнения данных операций соответственно .
find
Алгоритм поиска сам напрашивается из выше описанной структуры:
- если дерево пусто, то число не содержится в нашей структуре.
- если число равно полю или , то число в дереве есть.
- иначе ищем число в поддереве .
find(T, x)
if empty(T)
return false;
if T.min == x or T.max == x
return true;
return find(T.children[high(x)], low(x));
Заметим, что выполняя операцию , мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию столько раз, какова высота нашего дерева. На каждом уровне мы совершаем операций. Следовательно время работы .
insert
Операция вставки элемента состоит из нескольких частей:
- если дерево пусто или в нем содержится единственный элемент (), то присвоим полям и соответствующие значения. Делать что-то еще бессмысленно, так как информация записанная в и полностью описывает состояние текущего дерева и удовлетворяет структуре нашего дерева.
- иначе:
- если элемент больше или меньше текущего дерева, то обновим соответствующее значение минимума или максимума, а старый минимум или максимум добавим в дерево.
- вставим во вспомогательное дерево число , если соответствующее поддерево до этого было пусто.
- вставим число в поддерево , за исключением ситуации, когда текущее дерево — это 1-дерево, и дальнейшая вставка не требуется.
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)]
Нетрудно увидеть, что данная операция работает за время . На каждом уровне дерева мы выполняем операций. После этого возможны 2 случая: поддерево пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево , или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево пусто, то вставка в него будет выполнена за , так как мы всего лишь обновим поля и . Все остальные операции будут выполнятся уже со вспомогательным деревом , высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, . То есть операция вставки займет времени.
remove
Удаление из дерева также делится на несколько подзадач:
- если , значит в дереве один элемент, удалим его и отметим, что дерево пусто.
- если , то мы должны найти следующий минимальный элемент в этом дереве, присвоить значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум — это либо , либо (для случая действуем аналогично).
- если же и , то мы должны удалить из поддерева .
Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию . Также нельзя забывать, что если мы удаляем последнее вхождение , то мы должны удалить из вспомогательного дерева.
remove(T, x)
if T.min == x and T.max == x // случай, когда в дереве один элемент
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) // случай, когда элемента x нет в дереве
return;
remove(T.children[high(x)], low(x));
if empty(T.children[high(x)]) // если мы удалили из поддерева последний элемент
remove(T.aux, high(x)); // то удаляем информацию, что это поддерево не пусто
Оценка времени работы операции такая же, как и у операции . На каждом уровне дерева мы совершаем операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть .
next и prev
Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:
- если дерево пусто, или максимум этого дерева не превосходит , то следующего элемента в этом дереве не существует.
- если меньше поля , то искомый элемент и есть .
- если дерево содержит не более двух элементов, и , то искомый элемент .
- если же в дереве более двух элементов, то:
- если в дереве есть еще числа, большие , и чьи старшие биты равны , то продолжим поиск в поддереве , где будем искать число, следующее после .
- иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.
next(T, x)
if empty(T) or T.max <= x
return none; // следующего элемента нет
if T.min > x
return T.min;
if empty(T.aux)
return T.max; // в дереве не более двух элементов
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))); // случай, когда следующее число начинается с high(x)
else // иначе найдем следующее непустое поддерево
nextHigh = next(T.aux, high(x));
if nextHigh == null
return T.max; // если такого нет, вернем максимум
else
return merge(nextHigh, T.children[nextHigh].min); // если есть, вернем минимум найденного поддерева
Время работы, как и всех предыдущих функций, оценивается так же, и равно . Функция реализуется аналогично.
Преимущества и недостатки
Преимущества
Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у АВЛ, красно-черных, 2-3, splay и декартовых деревьев уже при небольшом количестве элементов. Конечно, из-за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:
- cортировка последовательности из чисел. Вставим элементы в дерево, найдем минимум и раз вызовем функцию . Так как все операции занимают не более времени, то итоговая асимптотика алгоритма , что даже лучше, чем цифровая сортировка, асимптотика которой .
- алгоритм Дейкстры. Данный алгоритм с использованием двоичной кучи для поиска минимума работает за , где — количество вершин в графе, а — количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не , а , и итоговая асимптотика этого алгоритма снизится до .
Недостатки
- существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
- другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее -битные числа, занимает памяти, что несложно доказывается индукцией, учитывая, что , где — количество памяти, занимаемое деревом, в котором хранятся -битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
