170
правок
Изменения
м
Нет описания правки
|definition=Пусть <tex>OPT(S)</tex> – оптимальное время работы бинарного дерева поиска для последовательности запросов <tex>S</tex>.
Если стоимость запросов в бинарном дереве поиска {{---}} <tex>O(n + OPT(S))</tex> для всей ключей от 1 до n, то дерево называется '''динамически оптимальным'''. Это свойство трудно показать. Неизвестно, есть ли какое-то динамически оптимальное online бинарное дерево поиска, и также неизвестно полиномиальное время для вычисления <tex>OPT(S) </tex> с точностью до константы.
Обозначим время работы динамически оптимального дерева <tex>O(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| Построение декартова дерева
