Викиконспекты - Вклад участника [ru]

Взвешенное дерево

2016-12-17T15:42:18Z

Algo1s097:

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

== Операции ==

{{Определение
|definition=Бинарное дерево поиска называется '''сбалансированным''', если половина вершин расположены слева от корня, а другая половина справа.
}}
Введем обозначения:
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
<tex>T</tex> — обозначение дерева,
<tex>root[T]</tex> — корень дерева <tex>T</tex>,
<tex>left[x]</tex> — левый сын вершины <tex>x</tex>,
<tex>right[x]</tex> — правый сын вершины <tex>x</tex>,
<tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя),
<tex>depth(x)</tex> — глубина вершины <tex>x</tex>. Это расстояние от неё до корня (количество ребер),
<tex>height(T)</tex> — глубина дерева <tex>T</tex>. Это глубина самой глубокой вершины дерева <tex>T</tex>,
<tex>weight(x)</tex> — вес вершины <tex>x</tex>. Это количество всех её дочерних вершин + 1 (она сама),
<tex>weight[T]</tex> — размер дерева <tex>T</tex>. Это количество вершин в нём (вес корня),
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева. Это максимальное значение, которое параметр <tex>weight[T]</tex> принимал с момента последней перебалансировки. Если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = weight[T]</tex>
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]

Синим цветом обозначены '''глубины''' вершин, а красным - их '''веса'''.
Считается вес вершины следующим образом: для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + <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>\mathtt{weight(left[x])} \leqslant \alpha \cdot weight(x)</tex> и <tex>\mathtt{weight(right[x])} \leqslant \alpha \cdot size(x)</tex>.}}

Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>weight[T]</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
=== Поиск элемента ===
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Применим стандартный алгоритм для двоичного дерева поиска - идем от корня, если значение в вершине равно значению искомого элемента, возвращаем, если значение в вершине меньше, то рекурсивно запускаемся от левого поддерева, если больше, то, соответственно, от левого.
'''Замечание:''' Дерево по ходу поиска искомой вершины ''не изменяется''.
Сложность операции поиска зависит от коэффициента <tex>\alpha</tex> и выражается формулой {{---}} <tex>\log_\frac{1}{\alpha} (N)</tex>

Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос - нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева — есть стек, в котором находится весь путь от корня к новой вершине. Берутся родителей из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
Есть 2 способа перебалансировки, {{---}} тривиальный и чуть более сложный.
====Тривиальный способ перебалансировки====
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
# Находится медиана на этом отрезке и подвешивается в качестве корня поддерева.
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
Данный способ требует <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
====Более сложный способ перебалансировки====
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот выбирается медиану, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.

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

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

Взвешенное дерево

2016-12-14T16:44:02Z

Algo1s097: /* Определение */

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

== Достоинства Scapegoat дерева ==
# Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у таких структур, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]]) 
# Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска <tex>O(log N)</tex>, в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>O(log N)</tex>) 
# Амортизированная сложность операций вставки и удаления <tex>O(log N)</tex> — это в общем-то аналогично остальным типам деревьев 
# При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева. 
== Недостатки Scapegoat дерева ==
# В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(log N)</tex>, но защиты от плохих случаев нет). 
# Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо. 
== Операции ==

{{Определение
|definition=Бинарное дерево поиска называется '''сбалансированным по весу''', если половина вершин расположены слева от корня, а другая половина справа.
}} 
'''Введем обозначения:''' 
Квадратные скобки в обозначениях означают, что мы храним это значение явно, а значит можем взять за время <tex>О(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
* <tex>T</tex> — обозначение дерева 
* <tex>root[T]</tex> — корень дерева <tex>T</tex> 
* <tex>left[x]</tex> — левый сын вершины x 
* <tex>right[x]</tex> — правый сын вершины x 
* <tex>brother(x)</tex> — брат вершины х (вершина, которая имеет с х общего родителя) 
* <tex>depth(x)</tex> — глубина вершины х. Это расстояние от неё до корня (количество ребер) 
* <tex>height(T)</tex> — глубина дерева T. Это глубина самой глубокой вершины дерева T 
* <tex>size(x)</tex> — вес вершины х. Это количество всех её дочерних вершин + 1 (она сама) 
* <tex>size[T]</tex> — размер дерева T. Это количество вершин в нём (вес корня) 
* <tex>maxsize[T]</tex> — максимальный размер дерева. Это максимальное значение, которое параметр <tex>size[T]</tex> принимал с момента последней перебалансировки. Если перебалансировка произошла только что, то <tex>maxsize[T] = size[T]</tex> 
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
 
Синим цветом обозначены '''глубины''' вершин, а красным - их '''веса'''.
 
В данном Scapegoat-дереве <tex>size[T] = 4</tex>, <tex>maxsize[T] \geqslant 4</tex>
 
* Коэффициeнт α — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
 {{Определение
|definition=Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен <tex>\alpha \cdot size(x)</tex> и вес ей правого сына меньше либо равен <tex>\alpha \cdot size(x)</tex>.}}
 
:<tex>size(left[x]) \leqslant \alpha \cdot size(x)</tex>; 
:<tex>size(right[x]) \leqslant \alpha \cdot size(x)</tex>; 

Перед тем как приступить к работе с деревом, мы выбираем параметр α в диапазоне <tex>[0.5; 1)</tex>. Также заводим две переменные для хранения текущих значений <tex>size[T]</tex> и <tex>maxsize[T]</tex> и обнуляем их. 
=== Поиск элемента ===
 Пусть мы хотим найти в данном Scapegoat дереве какой-то элемент. Применим стандартный алгоритм для двоичного дерева поиска - идем от корня, если значение в вершине равно значению искомого элемента, возвращаем, если значение в вершине меньше, то рекурсивно запускаемся от левого поддерева, если больше, то, соответственно, от левого. 
'''Замечание:''' Дерево по ходу поиска искомой вершины ''не изменяется''. 
Сложность операции поиска зависит от коэффициента <tex>\alpha</tex> и выражается формулой {{---}} <tex>log</tex>1/α<tex>(N)</tex>
 
Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к 0.5 мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: мы ищем Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу. 
Сразу возникает вопрос {{---}} Как делать перебалансировку найденной Scapegoat-вершины?
 Есть 2 способа перебалансировки, {{---}} ниже подробнее рассказывается о каждом из них.
====1 способ перебалансировки====
# Обходим всё поддерево Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получаем отсортированный список (свойство In-order обхода бинарного дерева поиска).
# Находим медиану на этом отрезке, подвешиваем её в качестве корня поддерева.
# Для «левого» и «правого» поддерева рекурсивно повторяем ту же операцию.
Данный способ требует <tex>O(size(Scapegoat-root))</tex> времени и столько же памяти.
====2 способ перебалансировки====
Мы вряд ли улучшим время работы перебалансировки — всё-таки каждую вершину нужно «подвесить» в новое место. Но мы можем попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот мы выбираем медиану, подвешиваем в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует нас и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, у нас будет ровно одно порождённое данным алгоритмом дерево. А откуда же мы взяли отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И мы можем эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — мы ведь этим затираем какую-то (возможно ещё не просмотренную) вершину — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(size(N))</tex>, а всего лишь <tex>O(log N)</tex>.

Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>log(3)</tex>.
=== Удаление элемента ===
Удаляем элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).
Далее проверяем выполнение условия: 
:<tex>size[T] < \alpha \cdot maxsize[T]</tex>; 
Если оно выполняется — дерево могло потерять α-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: 
:<tex>maxsize[T] = size[T]</tex>; 
==Вопросы==
 
*'''Как пройти от вершины вверх к корню? Нам нужно хранить ссылки на родителей?'''
:Поскольку мы пришли к месту вставки новой вершины из корня дерева — у нас есть стек, в котором находится весь путь от корня к новой вершине. Берём родителей из него.;
*'''Как посчитать вес вершины — ведь он не хранится в самой вершине?'''
:Для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + <tex>size(brother(x))</tex>.;
*'''Как посчитать <tex>size(brother(x))</tex>?'''
:Рекурсивно. Это займёт время <tex>O(size(brother(x)))</tex>. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность <tex>O(N)</tex> в худшем случае, о которой говорилось в начале. Но поскольку мы обходим поддерево α-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит <tex>O(log N)</tex>.;
*'''Что делать, если возникло несколько вершин, для которых нарушился α-балан?'''
:Ответ прост: выбрать можно любую.;
 
==Внешние ссылки==
*[https://en.wikipedia.org/wiki/Tree_traversal#In-order_.28symmetric.29 In-order обход дерева]
==Источники информации==
*[https://en.wikipedia.org/wiki/Scapegoat_tree Википедия - Scapegoat tree] 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья] 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]

Взвешенное дерево

2016-12-08T11:39:53Z

Algo1s097: Новая страница: «== Определение == '''Scapegoat-дерево''' (англ. ''Scapegoat-Tree'') {{---}} сбалансированное бинарное дерево п...»

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

== Достоинства Scapegoat дерева ==
# Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у таких структур, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]]) 
# Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска <tex>O(log N)</tex>, в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>O(log N)</tex>) 
# Амортизированная сложность операций вставки и удаления <tex>O(log N)</tex> — это в общем-то аналогично остальным типам деревьев 
# При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева. 
== Недостатки Scapegoat дерева ==
# В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(log N)</tex>, но защиты от плохих случаев нет). 
# Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо. 
== Операции ==

{{Определение
|definition=Бинарное дерево поиска называется '''сбалансированным по весу''', если половина вершин расположены слева от корня, а другая половина справа.
}} 
'''Введем обозначения:''' 
Квадратные скобки в обозначениях означают, что мы храним это значение явно, а значит можем взять за время <tex>О(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
* <tex>T</tex> — обозначение дерева 
* <tex>root[T]</tex> — корень дерева <tex>T</tex> 
* <tex>left[x]</tex> — левый сын вершины x 
* <tex>right[x]</tex> — правый сын вершины x 
* <tex>brother(x)</tex> — брат вершины х (вершина, которая имеет с х общего родителя) 
* <tex>depth(x)</tex> — глубина вершины х. Это расстояние от неё до корня (количество ребер) 
* <tex>height(T)</tex> — глубина дерева T. Это глубина самой глубокой вершины дерева T 
* <tex>size(x)</tex> — вес вершины х. Это количество всех её дочерних вершин + 1 (она сама) 
* <tex>size[T]</tex> — размер дерева T. Это количество вершин в нём (вес корня) 
* <tex>maxsize[T]</tex> — максимальный размер дерева. Это максимальное значение, которое параметр <tex>size[T]</tex> принимал с момента последней перебалансировки. Если перебалансировка произошла только что, то <tex>maxsize[T] = size[T]</tex> 
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
 
Синим цветом обозначены '''глубины''' вершин, а красным - их '''веса'''.
 
В данном Scapegoat-дереве <tex>size[T] = 4</tex>, <tex>maxsize[T] \geqslant 4</tex>
 
* Коэффициeнт α — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
 {{Определение
|definition=Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен <tex>\alpha \cdot size(x)</tex> и вес ей правого сына меньше либо равен <tex>\alpha \cdot size(x)</tex>.}}
 
:<tex>size(left[x]) \leqslant \alpha \cdot size(x)</tex>; 
:<tex>size(right[x]) \leqslant \alpha \cdot size(x)</tex>; 

Перед тем как приступить к работе с деревом, мы выбираем параметр α в диапазоне <tex>[0.5; 1)</tex>. Также заводим две переменные для хранения текущих значений <tex>size[T]</tex> и <tex>maxsize[T]</tex> и обнуляем их. 
=== Поиск элемента ===
 Пусть мы хотим найти в данном Scapegoat дереве какой-то элемент. Применим стандартный алгоритм для двоичного дерева поиска - идем от корня, если значение в вершине равно значению искомого элемента, возвращаем, если значение в вершине меньше, то рекурсивно запускаемся от левого поддерева, если больше, то, соответственно, от левого. 
'''Замечание:''' Дерево по ходу поиска искомой вершины ''не изменяется''. 
Сложность операции поиска зависит от коэффициента <tex>\alpha</tex> и выражается формулой {{---}} <tex>log</tex>1/α<tex>(N)</tex>
 
Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к 0.5 мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: мы ищем Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу. 
Сразу возникает вопрос {{---}} Как делать перебалансировку найденной Scapegoat-вершины?
 Есть 2 способа перебалансировки, {{---}} ниже подробнее рассказывается о каждом из них.
====1 способ перебалансировки====
# Обходим всё поддерево Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получаем отсортированный список (свойство In-order обхода бинарного дерева поиска).
# Находим медиану на этом отрезке, подвешиваем её в качестве корня поддерева.
# Для «левого» и «правого» поддерева рекурсивно повторяем ту же операцию.
Данный способ требует <tex>O(size(Scapegoat-root))</tex> времени и столько же памяти.
====2 способ перебалансировки====
Мы вряд ли улучшим время работы перебалансировки — всё-таки каждую вершину нужно «подвесить» в новое место. Но мы можем попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот мы выбираем медиану, подвешиваем в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует нас и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, у нас будет ровно одно порождённое данным алгоритмом дерево. А откуда же мы взяли отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И мы можем эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — мы ведь этим затираем какую-то (возможно ещё не просмотренную) вершину — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(size(N))</tex>, а всего лишь <tex>O(log N)</tex>.

Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>log(3)</tex>.
=== Удаление элемента ===
Удаляем элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).
Далее проверяем выполнение условия: 
:<tex>size[T] < \alpha \cdot maxsize[T]</tex>; 
Если оно выполняется — дерево могло потерять α-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: 
:<tex>maxsize[T] = size[T]</tex>; 
==Вопросы==
 
*'''Как пройти от вершины вверх к корню? Нам нужно хранить ссылки на родителей?'''
:Поскольку мы пришли к месту вставки новой вершины из корня дерева — у нас есть стек, в котором находится весь путь от корня к новой вершине. Берём родителей из него.;
*'''Как посчитать вес вершины — ведь он не хранится в самой вершине?'''
:Для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + <tex>size(brother(x))</tex>.;
*'''Как посчитать <tex>size(brother(x))</tex>?'''
:Рекурсивно. Это займёт время <tex>O(size(brother(x)))</tex>. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность <tex>O(N)</tex> в худшем случае, о которой говорилось в начале. Но поскольку мы обходим поддерево α-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит <tex>O(log N)</tex>.;
*'''Что делать, если возникло несколько вершин, для которых нарушился α-балан?'''
:Ответ прост: выбрать можно любую.;
 
==Внешние ссылки==
*[https://en.wikipedia.org/wiki/Tree_traversal#In-order_.28symmetric.29 In-order обход дерева]
==Источники информации==
*[https://en.wikipedia.org/wiki/Scapegoat_tree Википедия - Scapegoat tree] 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья] 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]

Файл:0ce162a62b624da8ba02233b4b254f23.png

2016-12-05T12:25:18Z

Algo1s097: Scapegoat дерево

Scapegoat дерево