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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «дерево размер мин макс вершина - дерево для корня из n элементов лист массив от 1 до sqrt(n) из…»)
 
Строка 1: Строка 1:
−
дерево
+
==Структура==
 +
Пусть есть множество <tex>m[0 .. M-1]</tex> мы хотим записать эти данный в дерево.
 +
В корне будут храниться: массив детей размером sqrt(M), значение текущего минимума и максимума в дерево, а также
 +
вспомогательный массив.
 +
Элемент массива из детей с индексом  <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для элементов <tex>[i*M^1/2 .. (i+1)M^1/2 - 1]</tex>
 +
В вспомогательном дереве хранится информация о том какие клетки уже заняты. То есть значение о хранится в вспомогательном дереве только если занят элемент с индексом j в массиве детей.
  
−
размер
 
−
мин макс
 
−
вершина - дерево для корня из n элементов
 
−
лист массив от 1 до sqrt(n) из дерево от корня из n
 
  
 +
Рассмотрим две опeрации
 +
Insert(x)
 +
Delete(x)
  
 +
==Insert==
 +
операция добавления(insert)пусть добавляем мы элемент <tex>x</tex>
 +
Если дерево пусто, то меняем значения минимума и максимума на 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 и меняем вспомогательное дерево.
 +
<pre>
 +
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)
 +
</pre>
  
 +
==Delete==
 +
Если 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 из вспомогательного дерева.
  
−
операция добавления(insert)
+
<pre>
−
Если дерево пусто, то мин и макс
+
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)
 +
</pre>

Версия 20:54, 15 июня 2011

Структура

Пусть есть множество [math]m[0 .. M-1][/math] мы хотим записать эти данный в дерево. В корне будут храниться: массив детей размером sqrt(M), значение текущего минимума и максимума в дерево, а также вспомогательный массив. Элемент массива из детей с индексом [math]i=\lfloor x/M^{1/2}\rfloor[/math] является также деревом для элементов [math][i*M^1/2 .. (i+1)M^1/2 - 1][/math] В вспомогательном дереве хранится информация о том какие клетки уже заняты. То есть значение о хранится в вспомогательном дереве только если занят элемент с индексом j в массиве детей.


Рассмотрим две опeрации Insert(x) Delete(x)

Insert

операция добавления(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)

Delete

Если 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)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_ван_Эмде_Боаса&oldid=10060»