170
правок
Изменения
Нет описания правки
'''Tango-дерево''' {{-- -}} online бинарное дерево поиска с временем работы <tex> O(\log \log N) </tex>, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.
Лучшая известная реализация на данный момент.
Время работы ''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>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
[[Файл:DariaPicture2.png|thumb|300px| t {{-- -}} наименьший общий предок х и у
]]
Если <tex>t = x</tex>, то есть <tex>x</tex> {{-- -}} предок <tex>y</tex> в момент <tex>i</tex>-го запроса,
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
Если <tex>t != y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
Если <tex>t = y</tex>, то есть <tex>y</tex> {{-- -}} предок <tex>x</tex> в момент <tex>j</tex>-го запроса,
Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.
Рассмотрим наше множество точек.
Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом {{-– --}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>
[[Файл:DariaPicture3.png|thumb|300px| Построение декартова дерева
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что <tex>OPT(x) >= M + 1/2* MP</tex>, где <tex>M</tex> {{-- -}} число запросов, <tex>MP</tex> {{--- }} максимальное число независимых прямоугольников.
То есть <tex>OPT(x) = \Omega(M + 1/2* MP)</tex>
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >= <tex>\sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{-- -}} число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
{{Определение
|definition='''Жирное ребро'''(''Prefered Path'') {{-- -}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
]]
Каждый из этих жирных путей организуем в свое ''splay'' -дерево.
Из каждой вершины создадим вспомогательную ссылку на корень ''splay'' -дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.
[[Файл:DariaPicture8.png|600px|
]]
Таким образом, все наши ключи организуют иерархичную структуру {{-- -}} ''Tango'' -дерево.
Каждый жирный путь {{-- -}} ''splay'' -дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына).
Глубина ''tango'' дерева <tex>\log n</tex>.
Время работы <tex>(M + K) * \log \log n</tex>, где <tex>K</tex> {{-- -}} число изменений жирных ребер.
<font color=green>Операций первого становления ребра жирным {{-- -}} ''O(\log n)'', это дает несущественный вклад в асимптотику. </font>
===Поиск===
Поиск элемента в <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> -дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, когда жирные ребра изменяются в результате поиска.
После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).
Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{-- -}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{--- }} максимальное значение в поддереве.
Во-вторых, нам понадобятся операции [http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево split] и [http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево merge], которые работают за <tex>O(\log k)</tex>, где <tex>k</tex> {{- --}} число узлов в <tex>splay</tex> - дереве.
Пусть для того, чтобы найти вершину <tex>x</tex>, которая находится в дереве <tex>F</tex>, мы прошли по тонкому ребру из вершины <tex>t</tex>, находящейся в дереве <tex>A</tex>.
Значит, нам нужно объединить деревья <tex>A</tex> и <tex>F</tex> и вырезать из дерева <tex>A</tex> подддерево <tex>D</tex>, в которое ведет жирное ребро из вершины <tex>t</tex>.
Пусть поддерево <tex>D</tex> {{-- -}} правое. Для левого аналогично.
# Так как мы знаем интервал значений <tex>[l', r']</tex> вершины <tex>t</tex> в ее правом поддереве <tex>D</tex>, сделаем по концам отрезка две операции <tex>split</tex>. Теперь мы можем отрезать поддерево <tex>D</tex>.
Таким образом,
перестройка = <tex>3 * split + 3 * merge = (O(1) + 3*O(\log \log n) + 3*O(\log \log n)) * K</tex>, где <tex>K</tex> {{-- -}} число изменений жирного ребра.
