170
правок
Изменения
→Динамическая оптимальность
{{Гипотеза
|statement=[http://neerc.ifmo.ru/wiki/index.php?title=Splay-дерево ''Splay''деревья] деревья обладают динамической оптимальностью.
То есть если мы разрешаем перестраивать деревья в процессе запроса, то ''splay'' деревья не больше, чем в константу хуже оптимальных.
Время работы ''splay'' дерева <tex>O(OPT dyn)</tex>
