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

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

Дерево ван Эмде Боаса — структура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале [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] — количество элементов в дереве.

Структура

корень дерева

Для удобства работы с деревом будем использовать [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;

find

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

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

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

insert

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

• Если дерево пусто, то меняем значения минимума и максимума на x;
• Если x<T.min тогда мы кладем T.min в поддерево i соответствующее T.min и ставим T.min = x. Если поддерево[i] до этого было пусто то мы также добавляем i в вспомогательное дерево.

Аналогично если x>T.max.

• Если T.min< x < T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево.

Insert(T, x)
  if (T.min > T.max)    // T is empty
    T.min = T.max = x;
    return
  if (T.min = T.max)
    if (x < T.min)
      T.min = x;
    if (x > T.max)
      T.max = x;
    return
  if (x < T.min)
    swap(x, T.min)
  if (x > T.max)
    swap(x, T.max)
  i = x/sqrt(M)
  Insert(T.children[i], x % sqrt(M))
  if (T.children[i].min = T.children[i].max)
    Insert(T.aux, i)

(с)wikipedia.org

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 из вспомогательного дерева.

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

Источники

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