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