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

Дерево ван Эмде Боаса (англ. Van Emde Boas tree, vEB tree) — структура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале [math][0;2^k)[/math] и осуществлять над ними все соответствующие дереву поиска операции.

Проще говоря, данная структура позволяет хранить [math]k[/math]-битные числа и производить над ними операции [math]\mathrm{find}[/math], [math]\mathrm{insert}[/math], [math]\mathrm{remove}[/math], [math]\mathrm{next}[/math], [math]\mathrm{prev}[/math], [math]\mathrm{\min}[/math], [math]\mathrm{max}[/math] и некоторые другие операции, которые присущи всем деревьям поиска.

Особенностью этой структуры является то, что все операции выполняются за [math]O(\log k)[/math], что асимптотически лучше, чем [math]O(\log n)[/math] в большинстве других деревьев поиска, где [math]n[/math] — количество элементов в дереве.

Структура

4-дерево, содержащее в себе 0, 1, 2, 3, 5, 14 и 15. Красным цветом выделены непустые поддеревья

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

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

Построим [math]k[/math]-дерево, при [math]k \neq 1[/math]. В нем будут хранится:

• массив [math]children[/math], состоящий из [math]2^{k/2}[/math] [math]k/2[/math]-деревьев
• вспомогательное [math]k/2[/math]-дерево, которое назовем [math]aux[/math]
• максимальный и минимальный элементы, хранящиеся в этом дереве (если оно не является пустым), причем дополнительно в массиве [math] chilren [/math] эти элементы хранить не будем.

Пусть у нас есть [math]k[/math]-битное число [math]x[/math]. Разобьем это число таким образом, что [math]\mathrm{high(x)}[/math] — число, соответствующее [math]k/2[/math] старшим битам числа [math]x[/math], а [math]\mathrm{low(x)}[/math] соответствует [math]k/2[/math] младшим битам. Тогда информация, хранится ли в данном дереве число [math]x[/math], эквивалентна информации, содержится ли в дереве [math]children[\mathrm{high(x)}][/math] число [math]\mathrm{low(x)}[/math].

Нетрудно увидеть, что высота подобного дерева [math]\log_{2} k[/math], так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.

Во вспомогательном дереве [math]aux[/math] будем хранить все такие числа [math]p[/math], что дерево [math]children[p][/math] не пусто.

Операции

empty

Чтобы определить, пусто ли дерево, будем изначально инициализировать поле [math]\min[/math] числом, которое не лежит в интервале [math][0;2^k)[/math]. Назовем это число [math]none[/math]. Например, это может быть [math]-1[/math], если мы храним в числа в знаковом целочисленном типе, или [math]2^k[/math], если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля [math]\min[/math] с этим числом.

boolean empty(t: Tree):
 if t.min == none
   return true
 else
  return false

min и max

Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля [math]\min[/math] или [math]\max[/math] в соответствии с запросом. Время выполнения данных операций соответственно [math]O(1)[/math].

find

Алгоритм поиска сам напрашивается из выше описанной структуры:

• если дерево пусто, то число не содержится в нашей структуре.
• если число равно полю [math]\min[/math] или [math]\max[/math], то число в дереве есть.
• иначе ищем число [math]\mathrm{low(x)}[/math] в поддереве [math]children[\mathrm{high(x)}][/math].

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))

Заметим, что выполняя операцию [math]\mathrm{find}[/math], мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию [math]\mathrm{find}[/math] столько раз, какова высота нашего дерева. На каждом уровне мы совершаем [math]O(1)[/math] операций. Следовательно время работы [math]O(\log k)[/math].

insert

Операция вставки элемента [math]x[/math] состоит из нескольких частей:

• если дерево пусто или в нем содержится единственный элемент ([math] \min = \max [/math]), то присвоим полям [math]\min[/math] и [math]\max[/math] соответствующие значения. Делать что-то еще бессмысленно, так как информация записанная в [math]\min[/math] и [math]\max[/math] полностью описывает состояние текущего дерева и удовлетворяет структуре нашего дерева.
• иначе:
  • если элемент [math]x[/math] больше [math]\max[/math] или меньше [math]\min[/math] текущего дерева, то обновим соответствующее значение минимума или максимума, а старый минимум или максимум добавим в дерево.
  • вставим во вспомогательное дерево [math]aux[/math] число [math]\mathrm{high(x)}[/math], если соответствующее поддерево [math]children[\mathrm{high(x)}][/math] до этого было пусто.
  • вставим число [math]\mathrm{low(x)}[/math] в поддерево [math]children[\mathrm{high(x)}][/math], за исключением ситуации, когда текущее дерево — это 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)]

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

remove

Удаление из дерева также делится на несколько подзадач:

• если [math] \min = \max = x [/math], значит в дереве один элемент, удалим его и отметим, что дерево пусто.
• если [math] x = \min [/math], то мы должны найти следующий минимальный элемент в этом дереве, присвоить [math]\min[/math] значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум — это либо [math] \max [/math], либо [math] children[aux.min].min [/math] (для случая [math] x = \max [/math] действуем аналогично).
• если же [math] x \neq \min [/math] и [math] x \neq \max [/math], то мы должны удалить [math]\mathrm{low(x)}[/math] из поддерева [math]children[\mathrm{high(x)}][/math].

Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию [math] merge [/math]. Также нельзя забывать, что если мы удаляем последнее вхождение [math]x[/math], то мы должны удалить [math]\mathrm{high(x)}[/math] из вспомогательного дерева.

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))                  // то удаляем информацию, что это поддерево не пусто

Оценка времени работы операции [math]\mathrm{remove}[/math] такая же, как и у операции [math]\mathrm{insert}[/math]. На каждом уровне дерева мы совершаем [math]O(1)[/math] операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало [math]O(1)[/math] операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть [math]O(\log k)[/math].

next и prev

Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:

• если дерево пусто, или максимум этого дерева не превосходит [math] x [/math], то следующего элемента в этом дереве не существует.
• если [math] x [/math] меньше поля [math] \min [/math], то искомый элемент и есть [math] \min [/math].
• если дерево содержит не более двух элементов, и [math] x \lt \max [/math], то искомый элемент [math] \max [/math].
• если же в дереве более двух элементов, то:
  • если в дереве есть еще числа, большие [math] x [/math], и чьи старшие биты равны [math]\mathrm{high(x)} [/math], то продолжим поиск в поддереве [math] children[\mathrm{high(x)}] [/math], где будем искать число, следующее после [math]\mathrm{low(x)} [/math].
  • иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.

int next(t: Tree, x: int)
 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                                                                  // иначе найдем следующее непустое поддерево 
     int nextHigh = next(t.aux, high(x));
     if nextHigh == -1
       return t.max;                                                     // если такого нет, вернем максимум
    else
       return merge(nextHigh, t.children[nextHigh].min);                 // если есть, вернем минимум найденного поддерева

Время работы, как и всех предыдущих функций, оценивается так же, и равно [math]O(\log k)[/math]. Функция [math]\mathrm{prev} [/math] реализуется аналогично.

Преимущества и недостатки

Преимущества

Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у АВЛ, красно-черных, 2-3, splay и декартовых деревьев уже при небольшом количестве элементов. Конечно, из-за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:

• cортировка последовательности из [math] n [/math] чисел. Вставим элементы в дерево, найдем минимум и [math] n - 1[/math] раз вызовем функцию [math] \mathrm{next} [/math]. Так как все операции занимают не более [math] O(\log k)[/math] времени, то итоговая асимптотика алгоритма [math] O(n \cdot \log k)[/math], что даже лучше, чем цифровая сортировка, асимптотика которой [math] O(n \cdot k)[/math].
• алгоритм Дейкстры. Данный алгоритм с использованием двоичной кучи для поиска минимума работает за [math] O(E \cdot \log V)[/math], где [math] V [/math] — количество вершин в графе, а [math] E [/math] — количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не [math] \log V [/math], а [math] \log k [/math], и итоговая асимптотика этого алгоритма снизится до [math] O(E \cdot \log k)[/math].

Недостатки

• существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
• другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее [math] k [/math]-битные числа, занимает [math] \Theta(2^k) [/math] памяти, что несложно доказывается индукцией, учитывая, что [math] S(2^k)=(2^{k/2} + 1) \cdot S(2^{k/2}) + O(2^{k/2})[/math], где [math] S(2^i) [/math] — количество памяти, занимаемое деревом, в котором хранятся [math] i [/math]-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются. Это делает дерево достаточно компактным, если оно содержит много элементов, потому что новые поддерево не создатся пока что-то не будет добавлено к нему. Первоначально каждый добавленный элемент, создает [math] O(\log k)[/math] новых деревьев, содержащих около [math]k/2[/math] элементов всего. По мере роста дерева, все больше и больше поддеревьев используются повторно, особенно крупные. В среднем это даёт заметное снижение потребления, памяти, например для для [math]k = 16[/math] массив из [math]4000[/math] элементов может занимать примерно в 16 раз меньше памяти.

См. также

• Поисковые структуры данных
• Дерево поиска
• Алгоритм Дейкстры

Источники информации

• Van Emde Boas tree — Wikipedia
• Дерево ван Эмде Боаса — habrahabr.ru