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

Структура данных которая содержит ассоциативный массив из m - битных чисел. Все операции в нем происходят за O([math]log(m)[/math]) = O([math]log (\lt tex\gt log(n)[/math])</tex>). При том, что все числа меньше n

Структура

Пусть есть множество [math]m[0 .. M-1][/math] мы хотим записать эти данный в дерево.

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

Будем называть наше дерево [math]T[/math]. В корне(root) будут храниться:

массив детей размером [math]sqrt M[/math] (T.children[])
значение текущего минимума и максимума в дерево (T.min, T.max)
вспомогательный массив (T.aux)

Элемент массива из детей с индексом [math]i=\lfloor x/M^{1/2}\rfloor[/math] является также деревом для множества [math][i sqrt(M)[/math] .. (i+1) sqrt(M)- 1]</tex>

В вспомогательном дереве хранится информация о том, какие клетки уже заняты. То есть значение [math]i[/math] хранится в вспомогательном дереве только если занят элемент с индексом [math]i[/math] в массиве детей.

Рассмотрим две опeрации Insert(x) Delete(T, 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

Delete

Удаление из дерева 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

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