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

Определение:

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

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

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

Структура

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

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

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

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

empty(T)
  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]low(x)[/math] в поддереве [math]children[high(x)][/math].

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

Заметим, что выполняя операцию [math]find[/math], мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию [math]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]high(x)[/math], если соответствующее поддерево [math]children[high(x)][/math] до этого было пусто.
  • вставим число [math]low(x)[/math] в поддерево [math]children[high(x)][/math], за исключением ситуации, когда текущее дерево — это 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)]

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

Нельзя забывать, что если мы удаляем последнее вхождение [math]x[/math], то мы должны удалить [math]high(x)[/math] из вспомогательного дерева.

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

Оценка времени работы операции [math]remove[/math] такая же, как и у операции [math]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] high(x) [/math], то продолжим поиск в поддереве [math] children[high(x)] [/math], где будем искать число, следующее после [math] low(x) [/math].
  • иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.

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

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);                 // если есть, вернем минимум найденного поддерева

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

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

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

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

• cортировка последовательности из [math] n [/math] чисел. Вставим элементы в дерево, найдем минимум и [math] n - 1[/math] раз вызовем функцию [math] 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] O(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]-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.

Источники

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