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

Материал из Викиконспекты
Перейти к: навигация, поиск
(insert)
(Структура)
(не показаны 53 промежуточные версии 7 участников)
Строка 1: Строка 1:
{{Определение
+
'''Дерево ван Эмде Боаса''' (англ. ''Van Emde Boas tree, vEB tree'') {{---}} структура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^k)</tex> и осуществлять над ними все соответствующие дереву поиска операции.
|definition=
+
 
'''Дерево ван Эмде Боаса''' {{---}} структура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^k)</tex> и осуществлять над ними все соответствующие дереву поиска операции.
+
Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>\mathrm{find}</tex>, <tex>\mathrm{insert}</tex>, <tex>\mathrm{remove}</tex>, <tex>\mathrm{next}</tex>, <tex>\mathrm{prev}</tex>, <tex>\mathrm{\min}</tex>, <tex>\mathrm{max}</tex> и некоторые другие операции, которые присущи всем деревьям поиска.
}}
 
Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>find</tex>, <tex>insert</tex>, <tex>remove</tex>, <tex>next</tex>, <tex>prev</tex>, <tex>min</tex>, <tex>max</tex> и некоторые другие операции, которые присущи всем деревьям поиска.
 
  
 
Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log k)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.
 
Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log k)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.
  
= Структура =
+
== Структура ==
[[Файл:Boas.jpg.jpg|right|378px|thumb|корень дерева]]
+
[[Файл:Дерево_ван_Эмде_Боаса.png|right|680px|thumb|4-дерево, содержащее в себе 0, 1, 2, 3, 5, 14 и 15. Красным цветом выделены непустые поддеревья]]
  
Для удобства работы с деревом будем использовать <tex>k</tex>, равные степени двойки.
+
Для удобства работы с деревом будем использовать <tex> k </tex>, равные степени двойки.
  
Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k)</tex>. Тогда 1-дерево хранит информацию, содержатся ли в нем 0 и 1.
+
Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k)</tex>. Тогда при <tex>k = 1</tex> дерево хранит информацию, содержатся ли в нем <tex>0</tex> и <tex>1</tex>.
  
Построим <tex>k</tex>-дерево, при <tex>k \neq 1</tex>. В нем будут хранится:
+
Построим <tex>k</tex>-дерево, при <tex>k \neq 1</tex>. В нем будут храниться:
 
*массив <tex>children</tex>, состоящий из <tex>2^{k/2}</tex>  <tex>k/2</tex>-деревьев
 
*массив <tex>children</tex>, состоящий из <tex>2^{k/2}</tex>  <tex>k/2</tex>-деревьев
 
*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</tex>
 
*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</tex>
*максимальный и минимальный элемент, хранящийся в этом дереве (если оно не является пустым)
+
*максимальный и минимальный элементы, хранящиеся в этом дереве (если оно не является пустым), причем дополнительно в массиве <tex> chilren </tex> эти элементы хранить не будем.
  
Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>high(x)</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>low(x)</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[high(x)]</tex> число <tex>low(x)</tex>.
+
Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>\mathrm{high(x)}</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>\mathrm{low(x)}</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[\mathrm{high(x)}]</tex> число <tex>\mathrm{low(x)}</tex>.
  
Нетрудно увидеть, что высота подобного дерева <tex>\ log_{2} k</tex>, так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.
+
Нетрудно увидеть, что высота подобного дерева <tex>\log_{2} k</tex>, так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.
  
 
Во вспомогательном дереве <tex>aux</tex> будем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</tex> не пусто.
 
Во вспомогательном дереве <tex>aux</tex> будем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</tex> не пусто.
  
= Операции =
+
== Операции ==
== empty ==
+
=== empty ===
Чтобы определить, пусто ли дерево, будем изначально инициализировать поле <tex>min</tex> числом, которое не лежит в интервале <tex>[0;2^k)</tex>. Назовем это число <tex>none</tex>. Например, это может быть <tex>-1</tex>, если мы храним в числа в знаковом целочисленном типе, или <tex>2^k</tex>, если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля <tex>min</tex> с этим числом.
+
Чтобы определить, пусто ли дерево, будем изначально инициализировать поле <tex>\min</tex> числом, которое не лежит в интервале <tex>[0;2^k)</tex>. Назовем это число <tex>none</tex>. Например, это может быть <tex>-1</tex>, если мы храним в числа в знаковом целочисленном типе, или <tex>2^k</tex>, если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля <tex>\min</tex> с этим числом.
<pre>
+
<code>
empty(T)
+
'''boolean''' empty(t: '''Tree'''):
   if T.min == none
+
   '''if''' t.min == ''none''
     return true;
+
     '''return''' ''true''
   else
+
   '''else'''
    return false;
+
  '''return''' ''false''
</pre>
+
</code>
  
== find ==
+
=== min и max ===
 +
Так как мы храним в дереве минимальное и максимальное значения, то данные операции не требуют ничего, кроме вывода значения поля <tex>\min</tex> или <tex>\max</tex> в соответствии с запросом. Время выполнения данных операций соответственно <tex>O(1)</tex>.
 +
 
 +
=== find ===
 
Алгоритм поиска сам напрашивается из выше описанной структуры:
 
Алгоритм поиска сам напрашивается из выше описанной структуры:
*если дерево пусто, то число не содержится в нашей структуре
+
*если дерево пусто, то число не содержится в нашей структуре.
*если число равно полю <tex>min</tex>, то число в дереве есть
+
*если число равно полю <tex>\min</tex> или <tex>\max</tex>, то число в дереве есть.
*иначе ищем число <tex>low(x)</tex> в поддереве <tex>children[high(x)]</tex>
+
*иначе ищем число <tex>\mathrm{low(x)}</tex> в поддереве <tex>children[\mathrm{high(x)}]</tex>.
  
<pre>
+
<code>
find(T, x)
+
'''boolean''' find(t: '''Tree''', x: '''int'''):
   if empty(T)
+
   '''if''' empty(t)
     return false;
+
     '''return''' ''false''
   if T.min == x
+
   '''if''' t.min == x '''or''' t.max == x
     return true;
+
     '''return''' ''true''
   return find(T.children[high(x)], low(x));
+
   '''return''' find(t.children[high(x)], low(x))
</pre>
+
</code>
  
== insert ==
+
Заметим, что выполняя операцию <tex>\mathrm{find}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>\mathrm{find}</tex> столько раз, какова высота нашего дерева. На каждом уровне мы совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>.
 +
 
 +
=== insert ===
 
Операция вставки элемента <tex>x</tex> состоит из нескольких частей:
 
Операция вставки элемента <tex>x</tex> состоит из нескольких частей:
  
*если дерево пусто, то присвоим полям <tex>min</tex> и <tex>max</tex> значение <tex>x</tex>. Делать что-то еще бессмысленно, так как информация записанная в <tex>min</tex> и <tex>max</tex> полностью описывает состояние текущего дерева.
+
*если дерево пусто или в нем содержится единственный элемент (<tex> \min = \max </tex>), то присвоим полям <tex>\min</tex> и <tex>\max</tex> соответствующие значения. Делать что-то еще бессмысленно, так как информация записанная в <tex>\min</tex> и <tex>\max</tex> полностью описывает состояние текущего дерева и удовлетворяет структуре нашего дерева.
 
*иначе:
 
*иначе:
**обновим поля <tex>min</tex> и <tex>max</tex> текущего дерева, если это требуется
+
**если элемент <tex>x</tex> больше <tex>\max</tex> или меньше <tex>\min</tex> текущего дерева, то обновим соответствующее значение минимума или максимума, а старый минимум или максимум добавим в дерево.
**вставим во вспомогательное дерево <tex>aux</tex> число <tex>high(x)</tex>, если соответствующее поддерево <tex>children[high(x)]</tex> до этого было пусто
+
**вставим во вспомогательное дерево <tex>aux</tex> число <tex>\mathrm{high(x)}</tex>, если соответствующее поддерево <tex>children[\mathrm{high(x)}]</tex> до этого было пусто.
**вставим число <tex>low(x)</tex> в поддерево <tex>children[high(x)]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется
+
**вставим число <tex>\mathrm{low(x)}</tex> в поддерево <tex>children[\mathrm{high(x)}]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется.
 +
 
 +
<code>
 +
'''function''' insert(t: '''Tree''', x: '''int'''):
 +
  '''if''' empty(t)                                    <span style="color:#008000">// проверка на пустоту текущего дерева</span>
 +
    t.min = x
 +
    t.max = x
 +
  '''else'''
 +
    '''if''' t.min == t.max                            <span style="color:#008000">// проверка, что в дереве один элемент</span>
 +
      '''if''' T.min < x
 +
        t.max = x
 +
      '''else'''
 +
        t.min = x
 +
  '''else'''
 +
      '''if''' t.min > x
 +
        swap(t.min, x)                          <span style="color:#008000">// релаксация минимума</span>
 +
      '''if''' t.max < x
 +
        swap(t.max, x)                          <span style="color:#008000">// релаксация максимума</span>
 +
      '''if''' t.k != 1
 +
        '''if''' empty(t.children[high(x)])
 +
          insert(t.aux, high(x))                <span style="color:#008000">// вставка high(x) во вспомогательно дерево aux</span>
 +
        insert(t.children[high(x)], low(x))      <span style="color:#008000">// вставка low(x) в поддерево children[high(x)]</span>
 +
</code>
 +
 
 +
Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[\mathrm{high(x)}]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[\mathrm{high(x)}]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>\min</tex> и <tex>\max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[\mathrm{high(x)}]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.
 +
 
 +
=== remove ===
 +
Удаление из дерева также делится на несколько подзадач:
 +
*если <tex> \min =  \max = x </tex>, значит в дереве один элемент, удалим его и отметим, что дерево пусто.
 +
*если <tex> x = \min </tex>, то мы должны найти следующий минимальный элемент в этом дереве, присвоить <tex>\min</tex> значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум {{---}} это либо <tex> \max </tex>, либо <tex> children[aux.min].min </tex> (для случая <tex> x = \max </tex> действуем аналогично).
 +
*если же <tex> x \neq \min </tex> и <tex> x \neq \max </tex>, то мы должны удалить <tex>\mathrm{low(x)}</tex> из поддерева <tex>children[\mathrm{high(x)}]</tex>.
 +
Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. Также нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>\mathrm{high(x)}</tex> из вспомогательного дерева.
 +
 
 +
<code>
 +
'''function''' remove(t: '''Tree''', x: '''int'''):
 +
  '''if''' t.min == x '''and''' t.max == x              <span style="color:#008000">// случай, когда в дереве один элемент</span>
 +
    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)                          <span style="color:#008000">// случай, когда элемента x нет в дереве</span>
 +
    '''return'''
 +
  remove(t.children[high(x)], low(x))
 +
  '''if''' empty(t.children[high(x)])            <span style="color:#008000">// если мы удалили из поддерева последний элемент</span>
 +
    remove(t.aux, high(x))                  <span style="color:#008000">// то удаляем информацию, что это поддерево не пусто</span>
 +
</code>
 +
 
 +
Оценка времени работы операции <tex>\mathrm{remove}</tex> такая же, как и у операции <tex>\mathrm{insert}</tex>. На каждом уровне дерева мы совершаем <tex>O(1)</tex> операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>.
 +
 
 +
=== next и prev ===
 +
Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:
 +
*если дерево пусто, или максимум этого дерева не превосходит <tex> x </tex>, то следующего элемента в этом дереве не существует.
 +
*если <tex> x </tex> меньше поля <tex> \min </tex>, то искомый элемент и есть <tex> \min </tex>.
 +
*если дерево содержит не более двух элементов, и <tex> x < \max </tex>, то искомый элемент <tex> \max </tex>.
 +
*если же в дереве более двух элементов, то:
 +
**если в дереве есть еще числа, большие <tex> x </tex>, и чьи старшие биты равны <tex>\mathrm{high(x)} </tex>, то продолжим поиск в поддереве <tex> children[\mathrm{high(x)}] </tex>, где будем искать число, следующее после <tex>\mathrm{low(x)} </tex>.
 +
**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.
 +
 
 +
<code>
 +
'''int''' next(t: '''Tree''', x: '''int''')
 +
  '''if''' empty(t) '''or''' t.max <= x
 +
    '''return''' ''none'';                                                          <span style="color:#008000">// следующего элемента нет</span>
 +
  '''if''' t.min > x
 +
    '''return''' t.min;
 +
  '''if''' empty(t.aux)
 +
    '''return''' t.max;                                                        <span style="color:#008000">// в дереве не более двух элементов</span>
 +
  '''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)));          <span style="color:#008000">// случай, когда следующее число начинается с high(x)</span>
 +
    '''else'''                                                                  <span style="color:#008000">// иначе найдем следующее непустое поддерево</span>
 +
      '''int''' nextHigh = next(t.aux, high(x));
 +
      '''if''' nextHigh == ''none''
 +
        '''return''' t.max;                                                    <span style="color:#008000">// если такого нет, вернем максимум</span>
 +
    '''else'''
 +
        '''return''' merge(nextHigh, t.children[nextHigh].min);                <span style="color:#008000"> // если есть, вернем минимум найденного поддерева</span>
 +
</code>
  
<pre>
+
Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex>\mathrm{prev} </tex> реализуется аналогично.
insert(T, x)
 
  if empty(T)                              // проверка на пустоту текущего дерева
 
    T.min = x;
 
    T.max = x;
 
  else
 
    if T.min > x
 
      T.min = x;                            // релаксация минимума
 
    if T.max < x
 
      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)]
 
</pre>
 
  
Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[high(x)]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[high(x)]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>min</tex> и <tex>max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[high(x)]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.
+
== Преимущества и недостатки ==
  
== remove ==
+
=== Преимущества ===
Удаление из дерева T также делится на несколько подзадач:
+
Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[2-3 дерево|2-3]], [[Splay-дерево|splay]] и [[Декартово дерево|декартовых]] деревьев уже при небольшом количестве элементов. Конечно, из-за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:
*Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее).
+
*cортировка последовательности из <tex> n </tex> чисел. Вставим элементы в дерево, найдем минимум и <tex> n - 1</tex> раз вызовем функцию <tex> \mathrm{next} </tex>. Так как все операции занимают не более <tex> O(\log k)</tex> времени, то итоговая асимптотика алгоритма <tex> O(n \cdot \log k)</tex>, что даже лучше, чем [[Цифровая сортировка|цифровая сортировка]], асимптотика которой <tex> O(n \cdot k)</tex>.
*Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].min.
+
*[[Алгоритм Дейкстры|алгоритм Дейкстры]]. Данный алгоритм с использованием [[Двоичная куча|двоичной кучи]] для поиска минимума работает за <tex> O(E \cdot \log V)</tex>, где  <tex> V </tex> {{---}} количество вершин в графе, а <tex> E </tex> {{---}} количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не <tex> \log V </tex>, а <tex> \log k </tex>, и итоговая асимптотика этого алгоритма снизится до <tex> O(E \cdot \log k)</tex>.
Аналогично для случая x = T.max
 
*Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x.
 
Важно, что Delete реализован рекурсивно от дерева в котором идет удаления.
 
Так же нельзя забывать, что если мы удаляем последнее вхождение x, то мы должны удалить i из вспомогательного дерева.
 
  
<pre>
+
=== Недостатки ===
Delete(T, x)
+
*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
  if (T.min == T.max == x)
+
*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> \Theta(2^k) </tex> памяти, что несложно доказывается индукцией, учитывая, что <tex> S(2^k)=(2^{k/2} + 1) \cdot S(2^{k/2}) + O(2^{k/2})</tex>, где <tex> S(2^i) </tex> {{---}} количество памяти, занимаемое деревом, в котором хранятся <tex> i </tex>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
    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
 
</pre>
 
== min и max ==
 
  
== next и prev ==
+
==См. также==
 +
* [[Поисковые структуры данных]]
 +
* [[Дерево поиска, наивная реализация|Дерево поиска]]
 +
* [[Алгоритм Дейкстры]]
  
= Источники =
+
== Источники информации ==
  
 
*[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]
 
*[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree Van Emde Boas tree — Wikipedia]
Строка 126: Строка 174:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Деревья поиска]]
 
[[Категория: Деревья поиска]]
 +
[[Категория: Структуры данных]]

Версия 14:57, 31 мая 2018

Дерево ван Эмде Боаса (англ. 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 == none
       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]-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.

См. также

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