Редактирование: Взвешенное дерево

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

== Операции ==
<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=Некоторая вершина <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>.}} 


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

=== Структура вершины ===

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

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

Таким образом, сложность получается логарифмическая, '''но!''' При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную  скорость поиска. При <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>-сбалансированность по весу. 
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
====Тривиальный способ перебалансировки====
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
# Находится медиана на этом отрезке и подвешивается в качестве корня поддерева.
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
Данный способ требует  <tex>O\mathtt{(weight(Scapegoat-root))}</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

=== Удаление элемента ===
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). 
Далее следует проверка выполнения условия: 
:<tex>weight[T] < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = weight[T]</tex>;

====Псевдокод====

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

*<tex>k</tex> {{---}} ключ, который будет удален.
 '''Delete'''(k): 
   deleted = '''DeleteKey'''(k)
   '''if''' deleted:
      '''if''' T.size < (T.α · T.maxSize):
         '''RebuildTree'''(T.size, T.root)

==Сравнение с другими деревьями==
===Достоинства 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://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья]<br>
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Деревья поиска]]