Взвешенное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение == '''Scapegoat-дерево''' (англ. ''Scapegoat-Tree'') {{---}} сбалансированное бинарное дерево п...»)
 
(Структура вершины n)
 
(не показаны 44 промежуточные версии 4 участников)
Строка 1: Строка 1:
== Определение ==
+
'''Scapegoat-tree''' {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее время поиска {{---}} <tex>O(\log N)</tex>, и  амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
'''Scapegoat-дерево''' (англ. ''Scapegoat-Tree'') {{---}} сбалансированное бинарное дерево поиска, обеспечивающее наихудшее <tex>O(log N)</tex> время поиска, и <tex>O(log N)</tex> - амортизирующее время вставки и удаления элемента.
+
В отличие от большинства других самобалансирующихся бинарных деревьев поиска, которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска : узел хранит только ключ и два указателя на своих потомков.  
 
  
== Достоинства Scapegoat дерева ==
 
# Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у таких структур, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]])<br><br>
 
# Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска <tex>O(log N)</tex>, в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>O(log N)</tex>)<br><br>
 
# Амортизированная сложность операций вставки и удаления <tex>O(log N)</tex> — это в общем-то аналогично остальным типам деревьев<br><br>
 
# При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления    операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.<br><br>
 
== Недостатки Scapegoat дерева ==
 
# В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(log N)</tex>, но защиты от плохих случаев нет).<br><br>
 
# Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.<br><br>
 
 
== Операции ==
 
== Операции ==
 +
<center>
 +
{| class="wikitable"
 +
|-
 +
! rowspan="2" | Операции
 +
! colspan="2" | Insert
 +
! colspan="2" | Delete
 +
! colspan="2" | Search
 +
! colspan="2" | Память
 +
|-
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
|-
 +
| Scapegoat-tree
 +
| align="center" style="background: #ddffdd;" | <tex>O(log\ n)</tex>
 +
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log\ n)</tex>
 +
| align="center" style="background: #ddffdd;" | <tex>O(log n)</tex>
 +
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log\ n)</tex>
 +
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(log\ n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
|}
 +
</center>
 +
===Обозначения и Определения===
  
 +
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
 +
 +
<tex>\mathtt{T}</tex> — обозначение дерева,
 +
 +
<tex>\mathtt{root[T]}</tex> — корень дерева <tex>T</tex>,
 +
 +
<tex>\mathtt{left[x]}</tex> — левый сын вершины <tex>x</tex>,
 +
 +
<tex>\mathtt{right[x]}</tex> — правый сын вершины <tex>x</tex>,
 +
 +
<tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя),
 +
 +
<tex>\mathtt{depth(x)}</tex> — глубина вершины <tex>x</tex> (количество рёбер от нее до корня),
 +
 +
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex> (глубина самой глубокой вершины дерева <tex>T</tex>),
 +
 +
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex> (количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
 +
 +
<tex>\mathtt{weight[T]}</tex> — размер дерева <tex>T</tex> (количество вершин в нём),
 +
 +
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева (максимальное значение, которое параметр <tex>\mathtt{weight[T]}</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
 +
 +
[[Файл:0ce162a62b624da8ba02233b4b254f23.png|380px|right]]
 +
 +
Синим цветом обозначены '''глубины''' вершин, а красным {{---}} их '''веса'''.
 +
Считается вес вершины следующим образом: для новой вершины вес равен <tex>1</tex>. Для её родителя <tex>\mathtt{weight} = 1</tex> (вес новой вершины) <tex>+ 1</tex> (вес самого родителя) <tex>+ \mathtt{weight(brother(x))}</tex>.
 +
Возникает вопрос {{---}} как посчитать <tex>\mathtt{weight(brother(x))}</tex>? Делается это рекурсивно. Это займёт время <tex>O\mathtt{(weight(brother(x)))}</tex>. Понимая, что в худшем случае  придётся посчитать вес половины дерева — здесь появляется та самая сложность <tex>O(N)</tex> в худшем случае, о которой говорилось в начале. Но поскольку совершается обход поддерева <tex>\alpha</tex>-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит <tex>O(\log N)</tex>.
 +
В данном Scapegoat-дереве <tex>weight[T] = 4</tex>, <tex>\mathtt{maxweight[T]} \geqslant 4</tex>
 +
 +
Коэффициeнт <tex>\alpha</tex> — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
 
{{Определение
 
{{Определение
|definition=Бинарное дерево поиска называется '''сбалансированным по весу''', если половина вершин расположены слева от корня, а другая половина справа.
+
|definition=Некоторая вершина <tex>x</tex> называется '''<tex>\alpha</tex>-сбалансированной по весу''', если <tex>\mathtt{weight(left[x])} \leqslant \alpha  \cdot \mathtt{weight(x)}</tex> и <tex>\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}</tex>.}}
}}<br><br>
+
 
'''Введем обозначения:'''<br><br>
+
 
Квадратные скобки в обозначениях означают, что мы храним это значение явно, а значит можем взять за время <tex>О(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
+
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>\mathtt {weight[T]}</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
* <tex>T</tex> — обозначение дерева<br><br>
+
 
* <tex>root[T]</tex> — корень дерева <tex>T</tex><br><br>
+
=== Структура вершины ===
* <tex>left[x]</tex> — левый сын вершины x<br><br>
+
 
* <tex>right[x]</tex> — правый сын вершины x<br><br>
+
'''struct''' Node:
* <tex>brother(x)</tex> — брат вершины х (вершина, которая имеет с х общего родителя)<br><br>
+
  '''T''' key                  <font color=green> //значение в вершине </font>
* <tex>depth(x)</tex> — глубина вершины х. Это расстояние от неё до корня (количество ребер)<br><br>
+
  '''Node''' left              <font color=green> //левый ребенок вершины </font>
* <tex>height(T)</tex> — глубина дерева T. Это глубина самой глубокой вершины дерева T<br><br>
+
  '''Node''' right              <font color=green> //правый ребенок вершины </font>
* <tex>size(x)</tex> — вес вершины х. Это количество всех её дочерних вершин + 1 (она сама)<br><br>
+
  '''Node''' height            <font color=green> //высота поддерева данной вершины </font>
* <tex>size[T]</tex> — размер дерева T. Это количество вершин в нём (вес корня)<br><br>
+
  '''Node''' depth              <font color=green> //глубина вершины </font>
* <tex>maxsize[T]</tex> — максимальный размер дерева. Это максимальное значение, которое параметр <tex>size[T]</tex> принимал с момента последней перебалансировки.<br><br> Если перебалансировка произошла только что, то <tex>maxsize[T] = size[T]</tex><br><br>
+
  '''Node''' parent            <font color=green> //ссылка на родителя </font>
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
+
  '''Node''' sibling            <font color=green> //ссылки на "братьев" данной вершины </font>
<br><br>
 
Синим цветом обозначены '''глубины''' вершин, а красным - их '''веса'''.
 
<br>
 
В данном Scapegoat-дереве <tex>size[T] = 4</tex>, <tex>maxsize[T] \geqslant 4</tex>
 
<br><br>
 
* Коэффициeнт α — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
 
<br>{{Определение
 
|definition=Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен  <tex>\alpha \cdot size(x)</tex> и вес ей правого сына меньше либо равен <tex>\alpha \cdot size(x)</tex>.}}
 
<br><br>
 
:<tex>size(left[x]) \leqslant \alpha  \cdot size(x)</tex>;<br><br>
 
:<tex>size(right[x]) \leqslant \alpha \cdot size(x)</tex>;<br><br>
 
  
Перед тем как приступить к работе с деревом, мы выбираем параметр α в диапазоне <tex>[0.5; 1)</tex>. Также заводим две переменные для хранения текущих значений <tex>size[T]</tex> и <tex>maxsize[T]</tex> и обнуляем их.<br><br>
 
 
=== Поиск элемента ===
 
=== Поиск элемента ===
<br>Пусть мы хотим найти в данном Scapegoat дереве какой-то элемент. Применим стандартный алгоритм для двоичного дерева поиска - идем от корня, если значение в вершине равно значению искомого элемента, возвращаем, если значение в вершине меньше, то рекурсивно запускаемся от левого поддерева, если больше, то, соответственно, от левого.<br><br>
+
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.
'''Замечание:''' Дерево по ходу поиска искомой вершины ''не изменяется''.<br>
+
 
Сложность операции поиска зависит от коэффициента <tex>\alpha</tex> и выражается формулой {{---}}  <tex>log</tex><sub>1/α</sub><tex>(N)</tex>
+
Таким образом, сложность получается логарифмическая, '''но!''' При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную  скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
<br><br>
+
 
Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к 0.5 мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную  скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
+
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
 +
*<tex>k</tex> {{---}} искомый ключ в дереве.
 +
 
 +
'''Search'''(root, k):
 +
  '''if ''' root = <tex>\varnothing</tex> or root.key = k:
 +
      '''return ''' root
 +
  '''else if ''' k <tex>\leqslant</tex> root.left.key:
 +
      '''return ''' Search(root.left, k)
 +
  '''else''':
 +
      '''return ''' Search(root.right, k)
 +
 
 
=== Вставка элемента ===
 
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: мы ищем Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной  стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу. <br><br>
+
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной  стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос {{---}} нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева —  есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.  
Сразу возникает вопрос {{---}} Как делать перебалансировку найденной Scapegoat-вершины?
+
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
<br><br>Есть 2 способа перебалансировки, {{---}} ниже  подробнее рассказывается о каждом из них.
+
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
====1 способ перебалансировки====
+
====Тривиальный способ перебалансировки====
# Обходим всё поддерево Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получаем отсортированный список (свойство In-order обхода бинарного дерева поиска).
+
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
# Находим медиану на этом отрезке, подвешиваем её в качестве корня поддерева.
+
# Находится медиана на этом отрезке и подвешивается в качестве корня поддерева.
# Для «левого» и «правого» поддерева рекурсивно повторяем ту же операцию.
+
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
Данный способ требует  <tex>O(size(Scapegoat-root))</tex> времени и столько же памяти.
+
Данный способ требует  <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
====2 способ перебалансировки====
+
 
Мы вряд ли улучшим время работы перебалансировки — всё-таки каждую вершину нужно «подвесить» в новое место. Но мы можем попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот мы выбираем медиану, подвешиваем в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует нас и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, у нас будет ровно одно порождённое данным алгоритмом дерево. А откуда же мы взяли отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И мы можем эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — мы ведь этим затираем какую-то (возможно ещё не просмотренную) вершину — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(size(N))</tex>, а всего лишь <tex>O(log N)</tex>.
+
==== Получение списка ====
 +
 
 +
*<tex>root</tex> {{---}} корень дерева, которое будет преобразовано в список.
 +
 
 +
'''FlattenTree'''(root, head):
 +
  '''if''' root = <tex>\varnothing</tex>:
 +
      '''return''' head
 +
  root.right = FlattenTree(root.right, head)
 +
  '''return''' FlattenTree(root.left, root)
 +
 
 +
==== Построение дерева ====
 +
 
 +
*<tex>size</tex> {{---}} число вершин в списке.
 +
*<tex>head</tex> {{---}} первая вершина в списке.
 +
 
 +
BuildHeightBalancedTree(size, head):
 +
  '''if''' size = 1 then:
 +
      return head
 +
  '''else if''' size = 2 then:
 +
      (head.right).left = head
 +
      '''return''' head.right
 +
  root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
 +
  last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
 +
  root.left = head
 +
  '''return''' last
 +
 
 +
==== Перестроение дерева ====
 +
 
 +
*<tex>size</tex> {{---}} число вершин в поддереве.
 +
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
 +
'''RebuildTree'''(size, scapegoat):
 +
  head = '''FlattenTree'''(scapegoat, <tex>\varnothing</tex>)
 +
  '''BuildHeightBalancedTree'''(size, head)
 +
  '''while''' head.parent <tex>\ne \varnothing </tex>
 +
      head = head.parent
 +
  '''return''' head
 +
 
 +
====Более сложный способ перебалансировки====
 +
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на <tex>1</tex> способ алгоритма внимательнее. Выбирается медиана, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. То есть для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.
 +
 
 +
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. То есть расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>\log(3)</tex>.
 +
Таким образом, если нужно сэкономить память, то <tex>2</tex> способ перебалансировки дерева {{---}} лучший вариант.
 +
 
 +
<center>
 +
{| cellpadding="0"
 +
| [[Файл:Good_insert_1.png|400px|thumb|Вставка без нарушения баланса 1]] || [[Файл:Good_insert_2.png|400px|thumb|Вставка без нарушения баланса 2]]
 +
|}
 +
{| cellpadding="0"
 +
|align="center"|[[Файл:Bad_insert.png|595px|thumb|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка]]
 +
|}
 +
</center>
 +
 
 +
====Псевдокод====
 +
 
 +
*<tex>n</tex> {{---}} узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
 +
 
 +
'''FindScapegoat'''(n):
 +
  size = 1
 +
  height = 0
 +
  '''while''' n.parent <tex>\ne \varnothing</tex>:
 +
      height = height + 1
 +
      totalSize = 1 + size + n.sibling.size()
 +
      '''if''' height <tex> > \lfloor \log_\frac{1}{\alpha} (totalSize) \rfloor</tex>:
 +
        '''return''' n.parent
 +
      n = n.parent
 +
      size = totalSize
 +
 
 +
Сама вставка элемента:
 +
 
 +
*<tex>k</tex> {{---}} ключ, который будет добавлен в дерево.
 +
 
 +
'''Insert'''(k):
 +
  height = InsertKey(k)
 +
  '''if''' height = −1:
 +
      '''return''' false;
 +
  '''else if''' height > T.hα:
 +
      scapegoat = '''FindScapegoat'''(Search(T.root, k))
 +
      '''RebuildTree'''(n.size(), scapegoat)
 +
  '''return''' true
  
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>log(3)</tex>.
 
 
=== Удаление элемента ===
 
=== Удаление элемента ===
Удаляем элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
+
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
Далее проверяем выполнение условия:<br>
+
Далее следует проверка выполнения условия:  
:<tex>size[T] < \alpha \cdot maxsize[T]</tex>;<br>
+
:<tex>\mathtt {weight[T]} < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять α-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:<br>
+
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>maxsize[T] = size[T]</tex>;<br>
+
:<tex>\mathtt {maxweight[T]} = \mathtt {weight[T]}</tex>;
==Вопросы==
+
 
<br>
+
====Псевдокод====
*'''Как пройти от вершины вверх к корню? Нам нужно хранить ссылки на родителей?'''
+
 
:Поскольку мы пришли к месту вставки новой вершины из корня дерева — у нас есть стек, в котором находится весь путь от корня к новой вершине. Берём родителей из него.;
+
Функция <tex>Delete(k)</tex> удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
*'''Как посчитать вес вершины — ведь он не хранится в самой вершине?'''
+
 
:Для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + <tex>size(brother(x))</tex>.;
+
*<tex>k</tex> {{---}} ключ, который будет удален.
*'''Как посчитать <tex>size(brother(x))</tex>?'''
+
'''Delete'''(k):
:Рекурсивно. Это займёт время <tex>O(size(brother(x)))</tex>. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность <tex>O(N)</tex> в худшем случае, о которой говорилось в начале. Но поскольку мы обходим поддерево α-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит <tex>O(log N)</tex>.;
+
  deleted = '''DeleteKey'''(k)
*'''Что делать, если возникло несколько вершин, для которых нарушился α-балан?'''
+
  '''if''' deleted:
:Ответ прост: выбрать можно любую.;
+
      '''if''' T.size < (T.α · T.maxSize):
<br><br>
+
        '''RebuildTree'''(T.size, T.root)
==Внешние ссылки==
+
 
*[https://en.wikipedia.org/wiki/Tree_traversal#In-order_.28symmetric.29 In-order обход дерева]
+
==Сравнение с другими деревьями==
 +
===Достоинства Scapegoat дерева===
 +
*  По сравнению с такими структурами, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]], нет необходимости хранить какие-либо дополнительные данные в вершинах (а значит появляется выигрыш по памяти).
 +
* Отсутствие необходимости перебалансировать дерево при операции поиска (а значит гарантируется максимальное время поиска <tex>O(\log N)</tex>, в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>O(\log N)</tex>)
 +
* При построении дерева выбирается некоторый коэффициент <tex>\alpha</tex>, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.
 +
===Недостатки Scapegoat дерева===
 +
* В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(\log N)</tex>, но защиты от плохих случаев нет).
 +
* Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента <tex>\alpha</tex> — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.
 +
 
 +
==См. также==
 +
* [[Поисковые структуры данных]]
 +
* [[АВЛ-дерево]]
 +
* [[Декартово дерево]]
 +
* [[Splay-дерево]]
 +
* [[Красно-черное дерево]]
 
==Источники информации==
 
==Источники информации==
 
*[https://en.wikipedia.org/wiki/Scapegoat_tree Википедия - Scapegoat tree]<br>
 
*[https://en.wikipedia.org/wiki/Scapegoat_tree Википедия - Scapegoat tree]<br>
 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья]<br>
 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья]<br>
 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]
 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Деревья поиска]]

Текущая версия на 16:14, 22 июня 2017

Scapegoat-tree — сбалансированное двоичное дерево поиска, обеспечивающее наихудшее время поиска — [math]O(\log N)[/math], и амортизирующее время вставки и удаления элемента — [math]O(\log N)[/math]. В отличие от большинства других самобалансирующихся бинарных деревьев поиска, которые обеспечивают худшем случае [math]O(\log N)[/math] время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.

Операции[править]

Операции Insert Delete Search Память
Среднее Худшее Среднее Худшее Среднее Худшее Среднее Худшее
Scapegoat-tree [math]O(log\ n)[/math] Амортизировано [math]O(log\ n)[/math] [math]O(log n)[/math] Амортизировано [math]O(log\ n)[/math] [math]O(log\ n)[/math] [math]O(n)[/math]

Обозначения и Определения[править]

Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время [math]O(1)[/math]. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.

[math]\mathtt{T}[/math] — обозначение дерева,

[math]\mathtt{root[T]}[/math] — корень дерева [math]T[/math],

[math]\mathtt{left[x]}[/math] — левый сын вершины [math]x[/math],

[math]\mathtt{right[x]}[/math] — правый сын вершины [math]x[/math],

[math]\mathtt{brother(x)}[/math] — брат вершины [math]x[/math] (вершина, которая имеет с [math]x[/math] общего родителя),

[math]\mathtt{depth(x)}[/math] — глубина вершины [math]x[/math] (количество рёбер от нее до корня),

[math]\mathtt{height(T)}[/math] — глубина дерева [math]T[/math] (глубина самой глубокой вершины дерева [math]T[/math]),

[math]\mathtt{weight(x)}[/math] — вес вершины [math]x[/math] (количество всех её дочерних вершин плюс [math]1[/math] — она сама),

[math]\mathtt{weight[T]}[/math] — размер дерева [math]T[/math] (количество вершин в нём),

[math]\mathtt{maxweight[T]}[/math] — максимальный размер дерева (максимальное значение, которое параметр [math]\mathtt{weight[T]}[/math] принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то [math]\mathtt{maxweight[T]} = \mathtt{weight[T]}[/math]

0ce162a62b624da8ba02233b4b254f23.png

Синим цветом обозначены глубины вершин, а красным — их веса. Считается вес вершины следующим образом: для новой вершины вес равен [math]1[/math]. Для её родителя [math]\mathtt{weight} = 1[/math] (вес новой вершины) [math]+ 1[/math] (вес самого родителя) [math]+ \mathtt{weight(brother(x))}[/math]. Возникает вопрос — как посчитать [math]\mathtt{weight(brother(x))}[/math]? Делается это рекурсивно. Это займёт время [math]O\mathtt{(weight(brother(x)))}[/math]. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность [math]O(N)[/math] в худшем случае, о которой говорилось в начале. Но поскольку совершается обход поддерева [math]\alpha[/math]-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит [math]O(\log N)[/math]. В данном Scapegoat-дереве [math]weight[T] = 4[/math], [math]\mathtt{maxweight[T]} \geqslant 4[/math]

Коэффициeнт [math]\alpha[/math] — это число в диапазоне от [math][0.5; 1)[/math], определяющее требуемую степень качества балансировки дерева.

Определение:
Некоторая вершина [math]x[/math] называется [math]\alpha[/math]-сбалансированной по весу, если [math]\mathtt{weight(left[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math] и [math]\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math].


Перед тем как приступить к работе с деревом, выбирается параметр [math]\alpha[/math] в диапазоне [math][0.5; 1)[/math]. Также нужно завести две переменные для хранения текущих значений [math]\mathtt {weight[T]}[/math] и [math]\mathtt{maxweight[T]}[/math] и обнулить их.

Структура вершины[править]

struct Node:
 T key                    //значение в вершине 
 Node left                //левый ребенок вершины 
 Node right               //правый ребенок вершины 
 Node height              //высота поддерева данной вершины 
 Node depth               //глубина вершины 
 Node parent              //ссылка на родителя 
 Node sibling             //ссылки на "братьев" данной вершины 

Поиск элемента[править]

Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет [math]O(\log_\frac{1}{\alpha} (N))[/math].

Таким образом, сложность получается логарифмическая, но! При [math]\alpha[/math] близком к [math]0.5[/math] мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При [math]\alpha[/math] близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к [math]O(N)[/math].

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

Вставка элемента[править]

Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить [math]\alpha[/math]-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян [math]\alpha[/math]-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос — нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева — есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий [math]\alpha[/math]-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить [math]\alpha[/math]-сбалансированность по весу. Сразу появляется вопрос — как делать перебалансировку найденной Scapegoat-вершины? Есть [math]2[/math] способа перебалансировки, — тривиальный и чуть более сложный.

Тривиальный способ перебалансировки[править]

  1. совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
  2. Находится медиана на этом отрезке и подвешивается в качестве корня поддерева.
  3. Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.

Данный способ требует [math]O\mathtt{(weight(Scapegoat-root))}[/math] времени и столько же памяти.

Получение списка[править]

  • [math]root[/math] — корень дерева, которое будет преобразовано в список.
FlattenTree(root, head):
  if root = [math]\varnothing[/math]:
     return head
  root.right = FlattenTree(root.right, head)
  return FlattenTree(root.left, root)

Построение дерева[править]

  • [math]size[/math] — число вершин в списке.
  • [math]head[/math] — первая вершина в списке.
BuildHeightBalancedTree(size, head):
  if size = 1 then:
     return head
  else if size = 2 then:
     (head.right).left = head
     return head.right
  root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
  last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
  root.left = head
  return last

Перестроение дерева[править]

  • [math]size[/math] — число вершин в поддереве.
  • [math]scapegoat[/math] — вершина, которая испортила баланс.
RebuildTree(size, scapegoat):
  head = FlattenTree(scapegoat, [math]\varnothing[/math])
  BuildHeightBalancedTree(size, head)
  while head.parent [math]\ne \varnothing [/math]
     head = head.parent
  return head

Более сложный способ перебалансировки[править]

Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на [math]1[/math] способ алгоритма внимательнее. Выбирается медиана, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. То есть для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не [math]O(weight(N))[/math], а всего лишь [math]O(\log N)[/math].

Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. То есть расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — [math]\log(3)[/math]. Таким образом, если нужно сэкономить память, то [math]2[/math] способ перебалансировки дерева — лучший вариант.

Вставка без нарушения баланса 1
Вставка без нарушения баланса 2
Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка

Псевдокод[править]

  • [math]n[/math] — узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
FindScapegoat(n):
  size = 1
  height = 0
  while n.parent [math]\ne \varnothing[/math]:
     height = height + 1
     totalSize = 1 + size + n.sibling.size()
     if height [math] \gt  \lfloor \log_\frac{1}{\alpha} (totalSize) \rfloor[/math]:
        return n.parent
     n = n.parent
     size = totalSize

Сама вставка элемента:

  • [math]k[/math] — ключ, который будет добавлен в дерево.
Insert(k):
  height = InsertKey(k)
  if height = −1:
     return false;
  else if height > T.hα:
     scapegoat = FindScapegoat(Search(T.root, k))
     RebuildTree(n.size(), scapegoat)
  return true

Удаление элемента[править]

Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). Далее следует проверка выполнения условия:

[math]\mathtt {weight[T]} \lt \alpha \cdot \mathtt {maxweight[T]}[/math];

Если оно выполняется — дерево могло потерять [math]\alpha[/math]-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:

[math]\mathtt {maxweight[T]} = \mathtt {weight[T]}[/math];

Псевдокод[править]

Функция [math]Delete(k)[/math] удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.

  • [math]k[/math] — ключ, который будет удален.
Delete(k): 
  deleted = DeleteKey(k)
  if deleted:
     if T.size < (T.α · T.maxSize):
        RebuildTree(T.size, T.root)

Сравнение с другими деревьями[править]

Достоинства Scapegoat дерева[править]

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

Недостатки Scapegoat дерева[править]

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

См. также[править]

Источники информации[править]