Изменения
→Структура вершины n
'''Scapegoat-tree''' {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее время поиска {{---}} <tex>O(\log N)</tex>, и амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска, которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
Коэффициeнт <tex>\alpha</tex> — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
{{Определение
|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>
=== Поиск элемента ===
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <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
=== Удаление элемента ===
==Источники информации==
*[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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Деревья поиска]]