Изменения

Танго '''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. ПоискПерестройка дереваЭто лучшая известная реализация на данный момент.

==Динамическая оптимальность==Если стоимость запросов в бинарном дереве поиска {{Определение |definition=Динамическая оптимальность ---}} <tex>O(Dynamic Optn + OPT(S))</tex> для всей ключей от <tex> 1 </tex> до <tex> n </tex>, то дерево называется '''динамически оптимальным'''.

 Если мы разрешаем перестраивать деревья в процессе запросаЭто свойство трудно показать. Неизвестно, есть ли какое-то splay-деревья не большединамически оптимальное online бинарное дерево поиска, и также неизвестно полиномиальное время для вычисления <tex>OPT(S)</tex> с точностью до константы.Обозначим время работы динамически оптимального дерева <tex>O(OPT_{dyn})</tex>, чем в константу хуже оптимальныхгде <tex>OPT_{dyn} = n + OPT(S)</tex>.

|statement=[[Splay-дерево | 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==Вторая нижняя оценка Уилберра (Wilber) ==.

Рассмотрим запрос То есть <tex>OPT(x) = \Omega(M + MP / 2)</tex>

Пусть левая граница <tex>= -inf</tex>, правая граница <tex>= +inf</tex>Вторая нижняя оценка Уилбера (Wilber) ==

Идем от ключа Для каждого запроса <tex>xx_{j}</tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключувычислим число Уилбера.

И каждый разРассмотрим запросы <tex>x_{i}, когда встречается значение большее, чем наше, но меньшее правой границы, мы сдвигаем правую границуi = 0..j</tex>

Пусть <tex>a < x_{j} < b</tex>, где <tex>a</tex> и <tex>b</tex> {{---}} левая и правая границы на момент <tex>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>b</tex> встретятся в <tex>x_{i} = x_{j}</tex>

Когда-то рано или поздно наши границы встретятся в Напишем <tex>r</tex>, если изменяется правая граница <tex>b</tex> и <tex>xl</tex> {{---}} если левая.

Напишем Получаем следующую оценку <tex>rOPT \geqslant \sum\limits_{j \in [1, n]} 1 + ch(j)</tex>Это можно вывести из предыдущей оценки, если меняется правая граница и построив соответствующее <tex>lch(j)</tex> - если леваямножество попарно независимых прямоугольников.

<tex>OPT >{{Определение |definition= \sum\limits_'''Жирное ребро''' (англ. ''Prefered edge'') {{i \in [1---}} ребро, n]соединяющее вершину с ее последним посещенным ребенком.}} 1 + ch(i)</tex>

|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 году. Лучшая известная реализация на данный момент.}}==Построение===

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

Рассмотрим бинарное дерево поиска[[Файл:DariaPicture7. png|400px| Изначально сделаем все левые ребра жирными.  <font color=green> // Из каждой вершины выходит <= 2 ребер. В общем случае одно жирное, другое нет. </font>]]

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

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

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

[[Файл:DariaPicture8.png|400px600px|

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

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

//Операций первого становления ребра жирным Глубина tango-дерева <tex>O(\log n)</tex> – дают несущественный вклад в асимптотику.

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

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

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

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

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

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

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

Поиск во всем ====Пример===='''Изменение жирных ребер в бинарном дереве = <tex>(log log n)</tex> * число проходов по нежирному ребру.поиска'''

====Пример====[[Файл:DariaPicture4.png|400px|]][[Файл:DariaPicture5.png|400px|]][[Файл:DariaPicture6.png|400px|]] '''Соответствие tango-дерева текущему бинарному дереву поиска'''

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

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

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

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

Во-первых, мы должны хранить в запомнить для каждой вершине вершины нашего splay изначального дерева поиска дополнительную информацию: Dep <tex>minChild</tex> {{-- глубину?? вершины , minDep - }} минимальное значение ребенка в поддереве текущей вершины, maxDep <tex>maxChild</tex> {{--- }} максимальное значение ребенка.Во-вторых, нам понадобятся операции split и merge, которые работают за O(log k), где k - число узлов в splay-деревеподдереве.

Пусть для тогоВо-вторых, чтобы найти вершину x, которая находилась в дереве Fнам понадобятся операции [[Splay-дерево | split]] и [[Splay-дерево | merge]], мы прошли по тонкому ребру из вершины tкоторые работают за <tex>O(\log k)</tex>, находящейся где <tex>k</tex> {{---}} число узлов в <tex>splay</tex>- дереве A.Значит, нам нужно объединить деревья A и F и вырезать из дерева A подддерево B, в которое ведет жирное ребро из вершины t.

Пусть поддерево B - правоедля того, чтобы найти вершину <tex>x</tex>, которая находится в дереве <tex>F</tex>, мы прошли по тонкому ребру из вершины <tex>t</tex>, находящейся в дереве <tex>A</tex>. Для левого аналогичноЗначит, нам нужно объединить деревья <tex>A</tex> и <tex>F</tex> и вырезать из дерева <tex>A</tex> подддерево <tex>D</tex>, в которое ведет жирное ребро из вершины <tex>t</tex>.

1) Так как мы знаем интервал значений [l', r'] вершины t в ее правом поддереве B, сделаем по концам отрезка две операции split. Теперь мы можем отрезать Пусть поддерево B.2) Мы знаем, что все ключи дерева F меньше t(так как бинарное дерево поиска), поэтому выполним операцию split по максимальному значению, меньшему t.3) Выполним операцию merge деревьев F и С.4) Выполним операцию merge деревьев FC и <tex>D</tex> {{---}} правое.5) Выполним операцию merge деревьев . и ..Для левого аналогично.

# Так как мы знаем интервал значений <tex>[l', r']</tex> вершины <tex>t</tex> в ее правом поддереве <tex>D</tex>, сделаем по концам отрезка две операции <tex>split</tex>. Теперь мы можем отрезать поддерево <tex>D</tex>.# Все ключи дерева <tex>F</tex> меньше <tex>t</tex> (так как бинарное дерево поиска), поэтому выполним операцию <tex>split</tex> по максимальному значению <tex>m</tex>, меньшему <tex>t</tex>.# Выполним операцию merge деревьев <tex>F</tex> и <tex>H</tex>.# Выполним операцию merge деревьев <tex>FH</tex> и <tex>G</tex>.# Выполним операцию merge деревьев <tex>FGH</tex> и <tex>E</tex>.# Проведем тонкое ребро от вершины <tex>t </tex> к дереву B<tex>D</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://www.lektorium.tv/lecture/14247 А.С.Станкевич, Дополнительные главы алгоритмов, 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]*[http://ocw.mak.ac.ug/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2010/lecture-notes/MIT6_851S10_lec02.pdf Prof. Erik Demaine, Advanced Data Structures]*[https://www.cs.princeton.edu/courses/archive/fall08/cos521/tango.pdf Sanjeev Arora, Competitive analysis of data structures]*[http://john2.poly.edu/papers/sicomp05/paper.pdf Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu, Dynamic Optimality—Almost] [[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]