Дерево ван Эмде Боаса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(insert)
(remove)
Строка 87: Строка 87:
  
 
== remove ==
 
== remove ==
Удаление из дерева T также делится на несколько подзадач:
+
Удаление из дерева также делится на несколько подзадач:
*Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее).
+
*Если <tex> min </tex> = <tex> max </tex> = <tex> x </tex>, значит в дереве один элемент, удалим его и отметим, что дерево пусто
*Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в  T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].min.
+
*Если <tex> x = min </tex>, то мы должны найти следующий минимальный элемент в этом дереве, присвоить <tex>min</tex> значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум {{---}} это либо <tex> max </tex>, либо <tex> children[aux.min].min </tex> (для случая <tex> x = max </tex> действуем аналогично)
Аналогично для случая x = T.max
+
*Если же <tex> x \neq min </tex> и <tex> x \neq max </tex>, то мы должны удалить <tex>low(x)</tex> из поддерева <tex>children[high(x)]</tex>.
*Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x.  
+
Нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>high(x)</tex> из вспомогательного дерева.
Важно, что Delete реализован рекурсивно от дерева в котором идет удаления.
 
Так же нельзя забывать, что если мы удаляем последнее вхождение x, то мы должны удалить i из вспомогательного дерева.
 
  
 
<pre>
 
<pre>
Delete(T, x)
+
remove(T, x)
   if (T.min == T.max == x)
+
   if T.min == x and T.max == x         // случай, когда в дереве один элемент
     T.min = M
+
     T.min = none;
     T.max = -1
+
     return;
     return
+
  if T.min == x
  if (x == T.min)
+
     if empty(T.aux)
     if (T.aux is empty)
+
      T.min = T.max;
       T.min = T.max
+
      return;
       return
+
    x = T.children[T.aux.min].min;
 +
    T.min = x;
 +
  if T.max == x
 +
     if empty(T.aux)
 +
       T.max = T.min;
 +
       return;
 
     else
 
     else
      x = T.children[T.aux.min].min
+
       x = T.children[T.aux.max].max;
      T.min = x
+
       T.max = x;
  if (x == T.max)
+
   if empty(T.aux)                       // случай, когда элемента x нет в дереве
    if (T.aux is empty)
+
     return;
      T.max = T.min
+
   remove(T.children[high(x)], low(x));
      return
+
   if empty(T.children[high(x)])         // если мы удалили из поддерева последний элемент
    else
+
     remove(T.aux, high(x));            // то удаляем информацию, что это поддерево не пусто
       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
 
 
</pre>
 
</pre>
 +
 
== next и prev ==
 
== next и prev ==
  

Версия 01:58, 8 апреля 2012

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

min и max

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

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 or T.max == x
    return true;
  return find(T.children[high(x)], low(x));

insert

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

  • если дерево пусто или в нем содержится единственный элемент ([math]min[/math] = [math]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 [/math] = [math] max [/math] = [math] 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 = T.children[T.aux.min].min;
    T.min = x;
  if T.max == x
    if empty(T.aux)
      T.max = T.min;
      return;
    else
      x = 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

Источники