Изменения

|statement=''[[Splay'' -дерево | Splay-деревья ]] обладают динамической оптимальностью.

Время Гипотетическое время работы ''splay'' -дерева <tex>O(OPT OPT_{dyn})</tex>

===Модель динамически оптимального дерева===

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

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

Рассмотрим систему координат ключ {{-- -}} время.Поставим точки, которые соответствуют обращению по данному ключу в определенное время.

|definition=Множество точек называется '''древесным''' (англ. ''aboral''), если выполняется следующее свойство:возьмем произвольный невырожденный прямоугольникна сторонах любого невырожденного (площадь прямоугольника больше нуля) с углами в наших прямоугольника, построенного на двух точках, как на противоположных вершинах (левая нижняя-правая верхняя или левая верхняя-правая нижняя), есть еще хотя бы одна точка.

[[Файл:DariaPicture1.png|thumb|left|400px|1) Запрос вершины 3 : вершина 3;  2) Запрос 2 : вершина 3 – вершина 1 – вершина 2;  

{{УтверждениеОпределение|statementdefinition=Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике '''Фазовая диаграмма (диаграмма состояния) работы с вершинами в наших точках есть еще хотя бы одна точкадеревом''' {{---}} графическое отображение состояния дерева, отличная от точекпри котором координата точки <tex>(x_{i}, на которых его построилиi)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени <tex>i</tex>.

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

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

[[Файл:DariaPicture2.png|400pxthumb|300px|t {{--- }} наименьший общий предок х и у

 Если <tex>t = x</tex>, то есть <tex>x</tex> {{-- -}} предок <tex>y</tex> в момент <tex>i</tex>-го запроса,

Если <tex>t != \ne y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника. Если <tex>t = y</tex>, то есть <tex>y</tex> {{--- }} предок <tex>x</tex> в момент <tex>j</tex>-го запроса,

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

Построим из них [[Декартово дерево | декартово(!) дерево]], где ключом будет ключ, а вспомогательным ключом – {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>. Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.

[[Файл:DariaPicture3.png|400px|thumb|right300px|построение Построение декартова дерева

 Но тогда рассмотрим прямоугольник(мы обращались к <tex>x</tex>) . А когда-то мы обратимся к <tex>y</tex>.

Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию. Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.

 Таким образом, мы получили какую-то ''offline '' оптимальность.

<tex>OPT (x) = omega\Omega(f) </tex> Если что-то работает за <tex>O(f * \cdot g)</tex>, значит это работает не более, чем в <tex>g</tex> раз хуже.

Можно показать, что <tex>OPT (x) \geqslant M + MP / 2</tex>, где <tex>= M</tex>({{---}} число запросов) + , <tex>MP</tex> {{---}} максимальное число независимых прямоугольников * 1/2.

То есть <tex>OPT(x) ==Вторая нижняя оценка Уилберра \Omega(WilberM + MP / 2) ==</tex>

Для ключа <tex>x_[j]</tex> рассмотрим ключи каждого запроса <tex>x_{i} : x_{I} = x_{j}, i = 0..j - 1</tex>вычислим число Уилбера.

Пусть Рассмотрим запросы <tex>a_{i} < x_{j} < b_{i}</tex>, где <tex>a_{i}</tex> и <tex>b_{i}</tex> -- левая и правая границы на момент i= 0.Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i} : x_{i} > a, x_{i} < x </tex>. Аналогично правую.В каждый момент времени позиция <tex>a_{i}</tex> может увеличиваться, <tex>b_{i}j</tex> уменьшаться.

Напишем Пусть <tex>ra < x_{j} < b</tex>, если изменяется где <tex>a</tex> и <tex>b</tex> {{---}} левая и правая граница границы на момент <tex>b_i</tex>.На момент времени <tex> i = 0 : a = -\infty, b = +\infty</tex>.Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i} : \{x_{j} < x_{i}< a\} </tex>. Аналогично правую.В каждый момент времени позиция <tex>a</tex> может увеличиваться, <tex>b</tex> уменьшаться.Рано или поздно, наши границы <tex>a</tex> и <tex>lb</tex> встретятся в <tex>x_{i} = x_{j}</tex> - если левая.

Напишем <tex>r</tex>, если изменяется правая граница <tex>b</tex> и <tex>l</tex> {{---}} если левая. {{Определение|definition='''Числом Уилберра Уилбера''' <tex>ch(ij)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.}}

<tex>OPT >= \geqslant \sum\limits_{i j \in [1, n]} 1 + ch(ij)</tex>Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(j)</tex> множество попарно независимых прямоугольников. [[Файл:DariaPicture12.png|300px]]

[[Файл:DariaPicture11{{Определение |definition='''Жирное ребро''' (англ.png|300px]]''Prefered edge'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.}}

|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>

Организуем их в полное двоичное [[Дерево поиска, наивная реализация | сбалансированное дерево]].Если <tex>n</tex> {{---}} не степень двойки, то на последний уровень будет заполнен не до конца.

Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).

Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >= \geqslant <tex>\sum\limits_{i \in [1, n]}K</tex> изменения числа , где <tex>K</tex> {{---}} число изменений жирных ребер.

То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слеваот нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.

{{Определение |definition='''Танго дерево''' - online бинарное дерево поиска с временем работы <tex> O(log log N) </tex>, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году. Лучшая известная реализация на данный момент.}}==Построение===

Время работы ''tango'' дерева <tex>O(OPT dyn * log log n)</tex> ===Построение===Рассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути.

|definition='''Жирное реброЖирный путь'''(англ. ''Prefered Pathpath'') {{- ребро--}} максимальный по включению путь, соединяющее вершину с ее последним посещенным ребенкомсостоящий из жирных ребер.

Рассмотрим бинарное дерево поиска[[Файл:DariaPicture7. png|400px|]]

Изначально сделаем все левые ребра жирнымиКаждый из этих жирных путей организуем в свое splay-дерево. Splay-дерево может быть построено как угодно.

Разобьем наше Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево , а не на жирные пути. [[Файл:DariaPicture7ребенка).png|400px|]]

Каждый из этих жирных путей организуем в свое Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.

Таким образом, все наши ключи организуют иерархичную структуру {{-- ''-}} Tango'' -дерево.

Каждый жирный путь {{-- ''-}} splay'' -дерево, и каждое их них каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)вершины по нежирному ребру.

Глубина ''tango'' -дерева <tex>\log n</tex>.

Время Общее время работы дерева <tex>(M + K) \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер) *, <tex> log log nM</tex>{{---}} число запросов.

<font color=green>Операций первого становления ребра жирным {{--- ''}} <tex>O(\log n)''</tex>, это дает несущественный вклад в асимптотику. </font>

Поиск элемента в <tex>tango</tex> -дереве схож с поиском в обычном дереве поиска.

Начинаем с поиска в жирном пути корня <tex>tango</tex> -дерева –{{--- <tex>}} splay</tex> -дереве.

Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелкав tango-дереве) и осуществим поиск в новом жирном пути(<tex>splay</tex> -дереве).

Поиск в <tex>splay</tex> -дереве(синемсинее дерево в splay-дереве) дереве = высота работает за высоту от количества вершин (количество вершин = длине {{---}} длина жирного пути = (<tex>\log n</tex>) = ) {{---}} то есть за <tex>\log \log n</tex>.

Поиск во всем дереве = соответствует <tex>(\log \log n)\cdot </tex> * число проходов по нежирному ребру.

[[Файл:DariaPicture4.png|300px400px|

[[Файл:DariaPicture5.png|300px400px|

[[Файл:DariaPicture6.png|300px400px|]] '''Соответствие tango-дерева текущему бинарному дереву поиска''' [[Файл:DariaPicture14.png|400px|]][[Файл:DariaPicture13.png|400px|]][[Файл:DariaPicture8.png|400px|

Для того, чтобы сохранить структуру <tex>tango</tex> -дерева (<tex>splay</tex> -дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, когда жирные ребра изменяются в результате поиска.

Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{-- -}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{--- }} максимальное значение в поддереве.

Во-вторых, нам понадобятся операции [[Splay-дерево | split ]] и [[Splay-дерево | merge]], которые работают за <tex>O(\log k)</tex>, где <tex>k</tex> {{- --}} число узлов в <tex>splay</tex> - дереве.

Пусть поддерево <tex>D</tex> {{-- -}} правое. Для левого аналогично.

# Все ключи дерева <tex>F</tex> меньше <tex>t</tex>(так как бинарное дерево поиска), поэтому выполним операцию <tex>split</tex> по максимальному значению <tex>m</tex>, меньшему <tex>t</tex>.

перестройка = <tex>(3 * \cdot split + 3 * \cdot merge</tex>, каждый из них за <tex>log log n ) \cdot K = (O(1) + 3*\cdot O(\log \log n) + 3*\cdot O(\log \log n))\cdot K</tex> * = <tex>O(\log \log n \cdot OPT_{dyn}) </tex>, где <tex>K</tex> {{---}} число изменений жирного ребра, <tex>n</tex> {{---}} число вершин в tango-дереве.

 Операции вставки и удаления в tango-дереве не поддерживаются. ==СсылкиИсточники информации==

*[http://erikdemaine.org/theses/dharmon.pdf Dion Harmon, New Bounds on Optimal Binary Search Trees]*[http://en.wikipedia.org/wiki/Tango_tree Wikipedia, {{---}} Tango tree]

[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]