170
правок
Изменения
Нет описания правки
===Поиск===
Поиск элемента в <tex>tango </tex> дереве схож с поиском в стандартном обычном дереве поиска.
Начинаем с поиска в жирном пути корня <tex>tango-</tex> дерева –- <tex>splay-</tex> дереве.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелка) и осуществим поиск останавливается на родителе корня поддерева, содержащего нужное значениев новом жирном пути(<tex>splay</tex> дереве).
Поиск во всем дереве = <tex>(log log n)</tex> * число проходов по нежирному ребру.
===Перестройка дерева===
Для того, чтобы сохранить структуру <tex>tango </tex> дерева (<tex>splay </tex> дерево соответствует текущему жирному пути), мы должны обновлять дерево его каждый раз, когда жирные ребра изменяются в результате поиска.
После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).
Во-первых, мы должны хранить в запомнить для каждой вершине вершины нашего splay изначального дерева поиска дополнительную информацию: Dep <tex>minChild</tex> - глубину?? вершины , minDep - минимальное значение ребенка в поддереве текущей вершины, maxDep <tex>maxChild</tex> -- максимальное значение ребенка.Во-вторых, нам понадобятся операции split и merge, которые работают за O(log k), где k - число узлов в splay-деревеподдереве.
Пусть поддерево B - правоедля того, чтобы найти вершину <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>[l', r']</tex> вершины <tex>t</tex> в ее правом поддереве <tex>D</tex>, сделаем по концам отрезка две операции <tex>split</tex>. Теперь мы можем отрезать поддерево <tex>D</tex>.# Все ключи дерева <tex>F</tex> меньше <tex>t</tex>(так как бинарное дерево поиска), поэтому выполним операцию <tex>split</tex> по максимальному значению <tex>m</tex>, меньшему <tex>t</tex>.# Выполним операцию merge деревьев <tex>F</tex> и <tex>H</tex>.# Выполним операцию merge деревьев <tex>FH</tex> и <tex>G</tex>.# Выполним операцию merge деревьев <tex>FGH</tex> и <tex>E</tex>.# Проведем тонкое ребро от вершины <tex>t </tex> к дереву B<tex>D</tex>.
Таким образом,
перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра.
====Пример====
