170
правок
Изменения
м
→Динамическая оптимальность
Время работы tango-дерева <tex>O(OPT dyn \cdot \log \log n)</tex>
==Динамическая оптимальность==
Рассмотрим для начала понятие динамической оптимальностипонятия online/offline динкамически/статически оптмального дерева поиска. {{Определение|definition=В '''статическом''' бинарном дереве поиска не происходит поворотов вокруг ребер. Его оптимальность зависит только от начального положения дерева. Это отличает его от '''динамического''' дерева, в котором повороты вокруг ребер разрешены.}} {{Определение|definition='''Offline дерево''' поиска получает все запросы сразу и может использовать дополнительную память и вычисления для нахождения наиболее оптимальной последовательности обработки запросов. Стоимость работы дерева поиска для заданной последовательности ключей это стоимость доступа к каждому ключу, и она не зависит от того, сколько времени мы потратили, чтобы найти оптимальную последовательность. '''Online дерево''' поиска ограничено в своих действиях, оно работает за время, пропорциональное стоимости исполнения запросов. Таким является splay-дерево.}}
{{Определение
