===Перестройка дерева===
Для того, чтобы сохранить структуру tango дерева (splay-дерево соответствует текущему жирному пути), мы должны обновлять дерево каждый раз, когда жирные ребра изменяются в результате поиска.
После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).
//Для того, чтобы это сделать эффективно, определим операции cut и join для жирного пути.
//Теперь Во-первых, мы изменяем жирное ребродолжны хранить в каждой вершине нашего splay дерева дополнительную информацию: Dep - глубину?? вершины , т е хотим отрезать 13 и подвесить 10 9//Отрезать 13 легкоminDep - минимальное значение ребенка текущей вершины, //maxDep - split по ключу, теперь х в корне, и отрезаем правое деревомаксимальное значение ребенка.// Как обратно вставить 9 10Merge в splayВо-дереве.<tex>T1<T2</tex> сливаем в <tex>Tвторых, T1</tex> – нам понадобятся операции split от самой большойи merge, которые работают за O(самой правойlog k) вершины, она становится конем, и где k - число узлов в правое поддерево приклеиваем <tex>Т2</tex>splay-дереве.
Но у нас <tex>T1</tex> не меньше<tex> T2</tex>Пусть для того, чтобы найти вершину x, которая находилась в дереве F, мы прошли по тонкому ребру из вершины t, находящейся в дереве A.Значит, нам нужно объединить деревья A и F и вырезать из дерева A подддерево B, в которое ведет жирное ребро из вершины t.
Посмотрим на общий случайПусть поддерево B - правое. Для левого аналогично.
Был жирный путь1) Так как мы знаем интервал значений [l', r'] вершины t в ее правом поддереве B, сделаем по концам отрезка две операции split. Теперь мы можем отрезать поддерево B.2) Мы знаем, что все ключи дерева F меньше t(так как бинарное дерево поиска), поэтому выполним операцию split по максимальному значению, меньшему t.3) Выполним операцию merge деревьев F и С.4) Выполним операцию merge деревьев FC и D.5) Выполним операцию merge деревьев . и ...
Мы в нем что-то искали, не нашли, остановились в вершине, и хотим другое ее поддерево подклеить в жирный путьПроведем тонкое ребро от вершины t к дереву B.
ЗаметимТаким образом, что ее жирный путь с одной стороны в левом поддереве нашей вершины. С другой стороны в правом поддереве какого-то предка. Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали. И вставим наше поддерево в жирный путь. Теперь надо отрезать старое жирное ребро. Закончили в какой-то вершине, лежащей в жирном пути. Надо посмотреть, в какую сторону вело жирное ребро. Оно вело туда, куда мы не шли. Мы знаем, что нужно вырезать из нашего дерева вершины, которые больше той, в которой мы закончили, но меньше того ключа, из которого мы последний раз шли не в ту сторону, в которую мы сейчас идем не по жирному ребру. Нас интересует ключ, который больше нашего, но который выше нас. Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей? Но это дерево примитивное, оно является полным двоичным. В нем можем предподсчитать для каждой вершины минимум и максимум. Значит, мы знаем интервал значений вершин его правого поддерева. И режем по минимальному и максимальному значениям в этом поддереве. Итого Разрезаем жирные ребра, по которым мы не прошли. Берем ребро. Берем дерево. Берем вершину. Split. Она корень. Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,вырезаем этот диапазон с помощью двух сплитов по <tex>r_{min}</tex> и по <tex>r_{max}</tex>.В новое независимое дерево ставим красный указатель на вершину. Старый красный указатель вел в дерево, которое надо слить с его предком. Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли. Перестройка перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра.
//Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,
//вырезаем этот диапазон с помощью двух сплитов по <tex>r_{min}</tex> и по <tex>r_{max}</tex>.
//В новое независимое дерево ставим красный указатель на вершину.
==Ссылки==
