170
правок
Изменения
Нет описания правки
<tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
{{Следствие Теорема !!следствие |statement=Рассмотрим <tex>n </tex> ключей и <tex>m </tex> запросов запросы x1 <tex>x_{1} .. xmx_{m}</tex>
Организуем их в полное двоичное сбалансированное дерево.
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что сумма по всем <tex>\sum\limits_{i (\in [1, n]} ch(i)) </tex> >= сумма по <tex>\sum\limits_{i \in [1, n]}</tex> изменения числа жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
===Пример===
[[Файл:DariaPicture4.png|400px|thumb|right300px|
]]
[[Файл:DariaPicture5.png|400px|thumb|right300px|
]]
[[Файл:DariaPicture6.png|400px|thumb|right300px|
]]
===Построение===
Пусть изначально все левые ребра были жирными.
Операций первого становления ребра жирным <tex>O(n)</tex> – дают не существенный несущественный вклад в асимптотику.
Глубина нашего дерева <tex>log n</tex>.Из каждой вершины выходит <= 2 ребер.В общем случае одно жирное, другое нет.Все наше дерево можно разбить на жирные пути .[[Файл:DariaPicture7.png|400px|thumb|right|
]]
Время работы (M + число изменений жирных ребер) *<tex> log log n</tex>
===Поиск===Поиск ключа <tex>x</tex>.
Ищем в корне tango-дерева – splay-дереве.
Если не нашли, значит надо идти по нежирному ребру.
Пойдем по нему(красная стрелка) и ищем в новом дереве.
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = <tex>log n</tex>) = <tex>log log n</tex>.
Поиск во всем дереве = <tex>(log log n)</tex> * число проходов по нежирному ребру.
===Перестройка дерева===
Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам.
Но у нас <tex>Т1</tex> не меньше<tex> Т2</tex>
Посмотрим на общий случай.Был жирный путь.
Мы в нем что-то искали, не нашли, остановились в вершине, и хотим другое ее поддерево подклеить в жирный путь.
Заметим, что ее жирный путь с одной стороны в левом поддереве нашей вершины.
С другой стороны в правом поддереве какого-то предка.
Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали.
