Изменения
Нет описания правки
'''Scapegoat-деревоtree''' {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее время поиска {{---}} <tex>O(\log N)</tex> , и амортизирующее время поиска, вставки и удаления элемента {{---}} <tex>O(\log N)</tex> {{---}} амортизирующее время вставки и удаления элемента.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
== Операции ==
===Обозначения и Определения===
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
<tex>T</tex> — обозначение дерева,
<tex>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>weight[T]</tex> принимал с момента последней перебалансировки.<br> Если , то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
Синим цветом обозначены '''глубины''' вершин, а красным {{- --}} их '''веса'''.Считается вес вершины следующим образом: для новой вершины вес = равен <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 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>O(\log_\frac{1}{\alpha} (N))</tex>.
Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
==Сравнение с другими деревьями==
===Достоинства Scapegoat дерева===
* По сравнению с такими структурами, как [[Красно-черное дерево]], [[АВЛ-дерево]] и [[Декартово дерево]], нет необходимости хранить какие-либо дополнительные данные в вершинах(а значит появляется выигрыш по памяти).
* Отсутствие необходимости перебалансировать дерево при операции поиска (а значит гарантируется максимальное время поиска <tex>O(\log N)</tex>, в отличии от структуры данных [[Splay-дерево]], где гарантируется только амортизированное <tex>O(\log N)</tex>)
* При построении дерева выбирается некоторый коэффициент <tex>\alpha</tex>, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.
