170
правок
Изменения
м
Нет описания правки
|statement=[[Splay-дерево | Splay-деревья]] обладают динамической оптимальностью.
То есть если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.
Гипотетическое время работы splay-дерева <tex>O(OPT OPT_{dyn})</tex>
}}
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.
Рассмотрим наше множество точек.
Построим из них [[http://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево Декартово дерево | декартово дерево]], где ключом будет ключ, а вспомогательным ключом {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>. Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
[[Файл:DariaPicture3.png|thumb|300px| Построение декартова дерева
|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>
Организуем их в полное двоичное [http://neerc.ifmo.ru/wiki/index.php?title=Дерево_поиска[Дерево поиска,_наивная_реализация наивная реализация | сбалансированное дерево]].
Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.
Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{---}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{---}} максимальное значение в поддереве.
Во-вторых, нам понадобятся операции [http://neerc.ifmo.ru/wiki/index.php?title=[Splay-дерево | split]] и [http://neerc.ifmo.ru/wiki/index.php?title=[Splay-дерево | merge]], которые работают за <tex>O(\log k)</tex>, где <tex>k</tex> {{---}} число узлов в <tex>splay</tex>- дереве.
Пусть для того, чтобы найти вершину <tex>x</tex>, которая находится в дереве <tex>F</tex>, мы прошли по тонкому ребру из вершины <tex>t</tex>, находящейся в дереве <tex>A</tex>.
