Scapegoat Tree — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
* В некоторых случаях операции модификации занимают <tex>O(n)</tex>, хотя из амортизированная сложность - <tex>O(\log n)</tex>.
 
* В некоторых случаях операции модификации занимают <tex>O(n)</tex>, хотя из амортизированная сложность - <tex>O(\log n)</tex>.
 
* За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.
 
* За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.
 +
 
== Операции ==
 
== Операции ==
 +
=== Поиск ===
 +
 +
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
 +
*<tex>k</tex> {{---}} искомый ключ в дереве.
 +
 +
'''Search'''(root, k):
 +
  '''if ''' root = null or root.key = k:
 +
      '''return ''' root
 +
  '''else if ''' k ≤ root.lef t.key:
 +
      '''return ''' Search(root.lef t, k)
 +
  '''else''':
 +
      '''return ''' Search(root.right, k)
 +
 +
=== Вставка элемента ===
 +
 +
Пока дерево остается <tex>\alpha</tex>-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция <tex>InsertKey(k)</tex> будет возвращать глубину данной вершины.
 +
 +
Нам нужна специальная функция <tex>FindScapegoat(n)</tex>, которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).
 +
 +
*<tex>n</tex> {{---}} узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
 +
 +
'''FindScapegoat'''(n):
 +
  size = 1
 +
  height = 0
 +
  '''while''' (n.parent <> null):
 +
      height = height + 1
 +
      totalSize = 1 + size + n.sibling.size()
 +
      '''if''' height > ⌊log1/α(totalSize)⌋:
 +
        '''return''' n.parent
 +
      n = n.parent
 +
      size = totalSize
 +
 +
 +
 +
  
 
== Оценка времени работы ==
 
== Оценка времени работы ==

Версия 14:11, 17 июня 2016

Scapegoat Tree — структура данных, представляющая собой частично сбалансированное дерево поиска (степень сбалансированности может быть настроена), такое что операции поиска, вставки и удаления работают за O(log n), при этом скорость одной операции может быть улучшена в ущерб другой.

Идея

При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить [math]O(\log n)[/math]. В Scapegoat Tree используется следующая идея: введем коэффициент [math]\alpha[/math], который показывает, насколько дерево может быть несбалансированным. Математически это выглядит следующим образом: [math] 1/2 \leqslant \alpha \leqslant 1 [/math]; [math] size(left[x]) \leqslant \alpha \cdot size(x) [/math]; [math] size(right[x]) \leqslant \alpha \cdot size(x) [/math], где [math]size(left[x])[/math] и [math]size(right[x])[/math] - размер левого и правого поддерева вершины [math]x[/math].

Если условие нарушается, запускается операция перебалансировки дерева. Заметим, что при [math]\alpha = 1[/math], деревом будет считаться даже линейная структура.

Свойства

Данная структура обладает следующими свойствами:

  • Выбор коэффициента [math]\alpha[/math] позволяет ускорить некоторые операции. Например, выбор большого значения [math]\alpha[/math] позволит выполнять очень много операций вставки, но замедлит операции поиска. При этом выбор коэффициента можно выполнять в процессе выполнения, опираясь на входные данные. Однако, неправильный выбор [math]\alpha[/math] приводит к сильному увеличению времени работы.
  • Не требуется проводить перебалансировку дерева при поиске, что гарантирует максимальное время работы поиска [math]O(\log n)[/math].
  • В некоторых случаях операции модификации занимают [math]O(n)[/math], хотя из амортизированная сложность - [math]O(\log n)[/math].
  • За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.

Операции

Поиск

  • [math]root[/math] — корень дерева или поддерева, в котором происходит поиск.
  • [math]k[/math] — искомый ключ в дереве.
Search(root, k):
  if  root = null or root.key = k:
     return  root
  else if  k ≤ root.lef t.key:
     return  Search(root.lef t, k)
  else:
     return  Search(root.right, k)

Вставка элемента

Пока дерево остается [math]\alpha[/math]-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция [math]InsertKey(k)[/math] будет возвращать глубину данной вершины.

Нам нужна специальная функция [math]FindScapegoat(n)[/math], которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).

  • [math]n[/math] — узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
FindScapegoat(n):
  size = 1
  height = 0
  while (n.parent <> null):
     height = height + 1
     totalSize = 1 + size + n.sibling.size()
     if height > ⌊log1/α(totalSize)⌋:
        return n.parent
     n = n.parent
     size = totalSize



Оценка времени работы