Изменения

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

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

Считается вес вершины следующим образом: для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + <brtex>\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>sizeweight[T] = 4</tex>, <tex>maxsize\mathtt{maxweight[T] } \geqslant 4</tex> Коэффициeнт <brtex>\alpha<br/tex>* Коэффициeнт α — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева. <br>{{Определение|definition=Некоторая вершина <tex>x </tex> называется "'''α-сбалансированной по весу"''', если вес её левого сына меньше либо равен <tex>\alpha \cdot size(x)</tex> и вес ей правого сына меньше либо равен <tex>\alpha \cdot size(x)</tex>.}} <br><br>:<tex>sizemathtt{weight(left[x]) } \leqslant \alpha \cdot sizeweight(x)</tex>;<br><br>:и <tex>size\mathtt{weight(right[x]) } \leqslant \alpha \cdot size(x)</tex>;<br><br>.}}  

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

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

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

Удаляем Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). Далее проверяем выполнение следует проверка выполнения условия:<br> :<tex>sizeweight[T] < \alpha \cdot maxsize\mathtt {maxweight[T]}</tex>;<br>Если оно выполняется — дерево могло потерять α<tex>\alpha</tex> -балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:<br>:<tex>maxsize\mathtt {maxweight[T] } = sizeweight[T]</tex>;<br>  ==ВопросыСравнение с другими деревьями==<br>===Достоинства Scapegoat дерева===*'''Как пройти от вершины вверх к корню? Нам нужно По сравнению с такими структурами, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]], нет необходимости хранить ссылки на родителей?''':Поскольку мы пришли к месту вставки новой вершины из корня дерева — у нас есть стек, какие-либо дополнительные данные в котором находится весь путь от корня к новой вершине. Берём родителей из неговершинах(а значит появляется выигрыш по памяти).;*'''Как посчитать вес вершины — ведь он не хранится в самой вершине?''':Для новой вершины вес = 1. Для её родителя вес = 1 Отсутствие необходимости перебалансировать дерево при операции поиска (вес новой вершины) + 1 (вес самого родителя) + а значит гарантируется максимальное время поиска <tex>sizeO(brother(x)\log N)</tex>.;*'''Как посчитать , в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>sizeO(brother(x)\log N)</tex>?'''):Рекурсивно. Это займёт время * При построении дерева выбирается некоторый коэффициент <tex>O(size(brother(x)))\alpha</tex>, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. ПонимаяМожно реализовать структуру данных, что в а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.===Недостатки Scapegoat дерева===* В худшем случае придётся посчитать вес половины операции модификации дерева — здесь появляется та самая сложность могут занять <tex>O(N)</tex> в худшем случае, о которой говорилось в начале. Но поскольку мы обходим поддерево α-сбалансированного по весу дерева можно показать, что времени (амортизированная сложность операции не превысит у них по-прежнему <tex>O(\log N)</tex>, но защиты от плохих случаев нет).;*'''Что делать, если возникло несколько вершин, для которых нарушился α-балан?''':Ответ прост: выбрать можно любую.;Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента <brtex>\alpha<br/tex>— в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.==Внешние ссылкиСм. также==*[https://en.wikipedia.org/wiki/Tree_traversal#In[Поисковые структуры данных]]* [[АВЛ-дерево]]* [[Декартово дерево]]* [[Splay-order_.28symmetric.29 Inдерево]]* [[Красно-order обход деревачерное дерево]]