Редактирование: Дерево ван Эмде Боаса

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 12: Строка 12:
 
Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k)</tex>. Тогда при <tex>k = 1</tex> дерево хранит информацию, содержатся ли в нем <tex>0</tex> и <tex>1</tex>.
 
Как уже было сказано выше, <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>
Строка 29: Строка 29:
 
  '''boolean''' empty(t: '''Tree'''):
 
  '''boolean''' empty(t: '''Tree'''):
 
   '''if''' t.min == ''none''
 
   '''if''' t.min == ''none''
     '''return''' ''true''
+
     '''return''' true
 
   '''else'''
 
   '''else'''
   '''return''' ''false''
+
   '''return''' false
 
</code>
 
</code>
  
Строка 46: Строка 46:
 
  '''boolean''' find(t: '''Tree''', x: '''int'''):
 
  '''boolean''' find(t: '''Tree''', x: '''int'''):
 
   '''if''' empty(t)
 
   '''if''' empty(t)
     '''return''' ''false''
+
     '''return''' false
 
   '''if''' t.min == x '''or''' t.max == 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))
 
</code>
 
</code>
Строка 104: Строка 104:
 
       '''return'''
 
       '''return'''
 
     x = merge(t.aux.min, t.children[t.aux.min].min)
 
     x = merge(t.aux.min, t.children[t.aux.min].min)
    t.min = x
+
  t.min = x
 
   '''if''' t.max == x
 
   '''if''' t.max == x
 
     '''if''' empty(t.aux)
 
     '''if''' empty(t.aux)
 
       t.max = t.min
 
       t.max = t.min
 
       '''return'''
 
       '''return'''
  '''else'''
+
  '''else'''
 
       x = merge(t.aux.max, t.children[t.aux.max].max)
 
       x = merge(t.aux.max, t.children[t.aux.max].max)
 
       t.max = x
 
       t.max = x
Строка 143: Строка 143:
 
     '''else'''                                                                  <span style="color:#008000">// иначе найдем следующее непустое поддерево</span>  
 
     '''else'''                                                                  <span style="color:#008000">// иначе найдем следующее непустое поддерево</span>  
 
       '''int''' nextHigh = next(t.aux, high(x));
 
       '''int''' nextHigh = next(t.aux, high(x));
       '''if''' nextHigh == ''none''
+
       '''if''' nextHigh == -1
 
         '''return''' t.max;                                                    <span style="color:#008000">// если такого нет, вернем максимум</span>
 
         '''return''' t.max;                                                    <span style="color:#008000">// если такого нет, вернем максимум</span>
 
     '''else'''
 
     '''else'''
Строка 160: Строка 160:
 
=== Недостатки ===
 
=== Недостатки ===
 
*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
 
*существенным недостатком данной структуры является то, что она позволяет хранить лишь целые неотрицательные числа, что существенно снижает область ее применения, по сравнению с другими деревьями поиска, которые не используют внутреннюю структуру элементов, хранящихся в них.
*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <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>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются.
+
*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <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>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются. Это делает дерево достаточно компактным, если оно содержит много элементов, потому что новые поддерево не создатся пока что-то не будет добавлено к нему. Первоначально каждый добавленный элемент, создает <tex> O(\log k)</tex> новых деревьев, содержащих около <tex>k/2</tex> элементов всего. По мере роста дерева, все больше и больше поддеревьев используются повторно, особенно крупные. В среднем это даёт заметное снижение потребления, памяти, например для  для <tex>k = 16</tex> массив из <tex>4000</tex> элементов может занимать примерно в 16 раз меньше памяти.
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: