Изменения

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