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