170
правок
Изменения
м
Пусть изначально все левые ребра были жирными.
Операций первого становления ребра жирным <tex>O(n)</tex> – дают несущественный вклад в асимптотикуРассмотрим бинарное дерево поиска.
Глубина нашего дерева <tex>log n</tex>{{Определение |definition=Жирное ребро("Prefered Path") - ребро, соединяющее вершину с ее последним посещенным ребенком.}} Изначально сделаем все левые ребра жирными.
Все Разобьем наше дерево можно разбить на жирные пути .
Нет описания правки
{{Определение
|definition=""Танго дерево "" - online бинарное дерево поиска с временем работы <tex> O(log log N) </tex>, создателями которого были Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.
Лучшая известная реализация на данный момент.
}}
]]
===Построение===
Из каждой вершины выходит <= 2 ребер.
В общем случае одно жирное, другое нет.
[[Файл:DariaPicture7.png|400px|
Каждый из этих жирных путей организуем в свое splay-дерево.
Из каждой вершины будет выходить вспомогательная ссылка создадим вспомогательную ссылку на корень splay-дерева, соответствующего жирному пути , в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.
[[Файл:DariaPicture8.png|400px|
]]
Таким образом, все наши ключи организуют иерархичную структуру-- Tango дерево.
Каждый жирный путь -- splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)
//Операций первого становления ребра жирным <tex>O(n)</tex> – дают несущественный вклад в асимптотику.
Глубина дерева <tex>log n</tex>.
Время работы (M + число изменений жирных ребер) *<tex> log log n</tex>
===Поиск===
Поиск ключа <tex>x</tex>.
