Изменения

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

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

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

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