170
правок
Изменения
Нет описания правки
Получим нижнюю оценку на оптимум.
<tex>OPT(x) = omega\Omega(f) </tex>
<font color=green>Если что-то работает за ''O(f * g)'', значит это работает не более, чем в ''g'' раз хуже.</font>
{{Определение
|definition='''Танго дерево''' - online бинарное дерево поиска с временем работы <tex> O(\log \log N) </tex>, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.
Лучшая известная реализация на данный момент.
}}
Время работы ''tango'' дерева <tex>O(OPT dyn * \log \log n)</tex>
===Построение===
Каждый жирный путь -- ''splay'' дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына).
Глубина ''tango'' дерева <tex>\log n</tex>.
Время работы (M + число изменений жирных ребер) *<tex> \log \log n</tex>
<font color=green>Операций первого становления ребра жирным -- ''O(\log n)'', это дает несущественный вклад в асимптотику. </font>
===Поиск===
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелка) и осуществим поиск в новом жирном пути(<tex>splay</tex> дереве).
Поиск в <tex>splay</tex> дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = <tex>\log n</tex>) = <tex>\log \log n</tex>.
Поиск во всем дереве = <tex>(\log \log n)</tex> * число проходов по нежирному ребру.
====Пример====
Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> -- минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> -- максимальное значение в поддереве.
Во-вторых, нам понадобятся операции split и 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>3 * split + 3 * merge</tex>, каждый из них за <tex>\log \log n = (O(1) + 3*O(\log \log n) + 3*O(\log \log n))</tex> * число изменений жирного ребра.
