170
правок
Изменения
Нет описания правки
{{Гипотеза
|statement=[http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево ''Splay'' ] деревья обладают динамической оптимальностью.
То есть если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.
Время работы ''splay'' дерева <tex>O(OPT dyn)</tex>
|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>.
Таким образом,
перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>\log \log n = (O(1) + 3*O(\log \log n) + 3*O(\log \log n))* K</tex> * , где <tex>K</tex> -- число изменений жирного ребра.
