Изменения

|definition=Динамическая оптимальность(Dynamic Opt)}} 

|statement=Splay-деревья обладают динамической оптимальностью.То есть время работы splay-дерева <tex>O(OPT dyn)</tex>

Рассмотрим ключи <tex>1..n </tex> и запросы x1<tex>x_{1}..xnx_{n}</tex>, где xi принадлежит <tex>x_{i} \in \{1..n\} </tex> – ключ, к которому мы обращаемся.

{{Утверждение|statement=Существует некоторое гипотетическое оптимальное дерево, которое на каждый запрос делает следующие вещи- # идет от корня до xi<tex>x_{i}</tex>- # делает какие-то количество поворотов}}

Время работы tango-дерева <tex>O(OPT dyn * log log n)</tex>

===Оценка снизу на динамический оптимум===

===Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска===

{{Определение|definition=Множество точек называется '''древесным ''' (aboral), если выполняется следующее свойство:

{{Утверждение|statement=Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике с вершинами в наших точках есть еще хотя бы одна точка, отличная от точек, на которых его построили.}} {{Теорема|statement=Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.

1) #Фазовая диаграмма работы с деревом поиска обралает обладает свойством древестности.

Пусть мы обращались к какому-то ключу <tex>x </tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y </tex> в <tex>j</tex>-ом запросе.

На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x </tex> и <tex>y </tex> -– вершину <tex>t</tex>.Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска он она находится между <tex>х </tex> и <tex>у</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>х</tex>, значит есть точка на стороне нашего многоугольника.

2) # Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.