170
правок
Изменения
Нет описания правки
Лучшая известная реализация на данный момент.
Время работы ''tango''-дерева <tex>O(OPT dyn * \log \log n)</tex>
==Динамическая оптимальность==
{{Гипотеза
|statement=[http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево ''Splay''-деревья] обладают динамической оптимальностью.То есть если мы разрешаем перестраивать деревья в процессе запроса, то ''splay''-деревья не больше, чем в константу хуже оптимальных.Время Гипотетическое время работы ''splay''-дерева <tex>O(OPT dyn)</tex>
}}
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.
Рассмотрим этот прямоугольник.
На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x</tex> и <tex>y</tex> {{-- -}} вершину <tex>t</tex>.
Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
]]
Каждый из этих жирных путей организуем в свое ''splay''-дерево.
Из каждой вершины создадим вспомогательную ссылку на корень ''splay''-дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.
[[Файл:DariaPicture8.png|600px|
]]
Таким образом, все наши ключи организуют иерархичную структуру {{---}} ''Tango''-дерево.
Каждый жирный путь {{---}} ''splay''-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына).
Глубина ''tango'' дерева <tex>\log n</tex>.
===Поиск===
Поиск элемента в <tex>tango</tex> -дереве схож с поиском в обычном дереве поиска.
Начинаем с поиска в жирном пути корня <tex>tango</tex> -дерева {{---}} <tex>splay</tex>-дереве.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелка) и осуществим поиск в новом жирном пути(<tex>splay</tex>-дереве).
Поиск в <tex>splay</tex>-дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = <tex>\log n</tex>) = <tex>\log \log n</tex>.
Поиск во всем дереве = <tex>(\log \log n)</tex> * число проходов по нежирному ребру.
===Перестройка дерева===
Для того, чтобы сохранить структуру <tex>tango</tex> -дерева (<tex>splay</tex>-дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, когда жирные ребра изменяются в результате поиска.
После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).
