Изменения

Танго '''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. 1)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>, значит есть точка на стороне нашего многоугольника.(Рис.2)

[[Файл:DariaPicture2.png|thumb|300px| t {{---}} наименьший общий предок х и у]]Если <tex>t = x</tex>, то есть х <tex>x</tex> {{--- }} предок у <tex>y</tex> в момент <tex>i</tex>-го запроса,тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.Найдем в дереве поиска наименьшего общего предка <tex>t </tex> вершин <tex>x </tex> и <tex>y </tex> на момент <tex>j</tex>-го запроса.Если t != y, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.Если t = y, то есть y - предок x в момент j-го запроса,Значит y «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от у к родителю.То есть во время i-го запроса y был в поддереве х, а во время j-го запроса х в поддереве у, значит где-то между этими моментами выполнялся поворот вокруг ребра от у к родителю, и мы обращались к у, следовательно есть точка на правой стороне нашего прямоугольника (рисунок надо?)

# Если <tex>t \ne y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.Если <tex>t = y</tex>, то есть <tex>y</tex> {{---}} предок <tex>x</tex> в момент <tex>j</tex>-го запроса,Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю. То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника. '''2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.'''

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

(рис[[Файл:DariaPicture3.3)png|thumb|300px| Построение декартова дерева??Декартово дерево становится такое]]

После этого мы должны перестроить наше дерево, изменив приоритеты.Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами.

У нас есть вершина х<tex>x</tex>, у которой есть правый сын у<tex>y</tex>, и приоритет у х <tex>x</tex> больше чем у у<tex>y</tex>, их надо поменять, то есть дотронуться до вершины у<tex>y</tex>, чего мы делать не хотели в этой строке.Но тогда рассмотрим прямоугольник(мы обращались к х<tex>x</tex>). А когда-то мы обратимся к <tex>y</tex>. Если есть точка на левой стороне, то к <tex>x</tex> мы обратимся раньше, чем к <tex>y</tex> следовательно неверно, что приоритет <tex>x</tex> больше чем приоритет <tex>y</tex>На левой стороне точек нет. Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у<tex>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.

Если на правой стороне есть точка на левой стороне, то сейчас мы бы обращались к х мы обратимся раньшеней, чем а не к у следовательно неверно, что приоритет х больше чем приоритет уНа левой стороне точек нет<tex>y</tex>.

Если на нижней верхней стороне есть точка<tex>z</tex> с ключом меньше <tex>y</tex>, значит есть точкамы будем обращаться к ней тогда же, когда и к которой <tex>y</tex>, значит мы обращались сейчас, ключ которой больше, чем у х, но меньше у, но тогда она должна быть нашим правым сыномможет перейти к прямоугольнику, а не вершина упостроенному на точках <tex>x</tex> и <tex>z</tex>.

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

Таким образом, мы получили какую-то ''offline'' оптимальность. Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно кол-во количество точек на диаграмме.

Оптимум <tex>OPT(x) = омега\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> {{---}} максимальное число независимых прямоугольников. То есть <tex>OPT(x) = \Omega(M + MP / 2)</tex> = сумме по всем запросам=Вторая нижняя оценка Уилбера (Wilber) == Для каждого запроса <tex>x_{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>l</tex> {{---}} если левая. {{Определение|definition='''Числом Уилбера''' <tex>ch(j)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.}} Получаем следующую оценку <tex>OPT \geqslant \sum\limits_{j \in [1, n]} 1 + ch(j)</tex>Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(j) </tex> множество попарно независимых прямоугольников. [[Файл:DariaPicture12.png|300px]] {{Определение |definition='''Жирное ребро''' (англ. ''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)\geqslant \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер. То есть если мы улучшили правую границу (мы искали что-то справа), а потом улучшили левую (искали слева от нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.}} == Tango-деревья== ===Построение=== Рассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути. {{Определение |definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирных ребер.}} [[Файл:DariaPicture7.png|400px|]] Каждый из этих жирных путей организуем в свое splay-дерево. Splay-дерево может быть построено как угодно. Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка). Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.   [[Файл:DariaPicture8.png|600px|]] Таким образом, все наши ключи организуют иерархичную структуру {{---}} Tango-дерево. Каждый жирный путь {{---}} splay-дерево, и каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит сын вершины по нежирному ребру. Глубина tango-дерева <tex>\log n</tex>. Общее время работы дерева <tex>(M + K) \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер, <tex>M</tex> {{---}} число запросов. Операций первого становления ребра жирным {{---}} <tex>O(\log n)</tex>, это дает несущественный вклад в асимптотику. ===Поиск=== Поиск элемента в tango-дереве схож с поиском в обычном дереве поиска. Начинаем с поиска в жирном пути корня tango-дерева {{---}} splay-дереве.  Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).

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

Следствие Рассмотрим Поиск во всем дереве соответствует <tex>(\log \log n ключей и m запросов запросы x1 .. xmОрганизуем их в полное двоичное сбалансированное дерево.(см рисунок)Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!тамДля каждой вершины будем запоминать ребро, \cdot </tex> число проходов по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро)нежирному ребру.

Утверждается, что сумма по всем i (ch(i)) >= сумма по i изменения числа ===Пример===='''Изменение жирных реберТо есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.в бинарном дереве поиска'''

Итак, '''Соответствие tango-деревьядерева текущему бинарному дереву поиска'''

Пример[[Файл:DariaPicture14.png|400px|поиск 5]](рис[[Файл:DariaPicture13. 4)png|400px|поиск 10]](рис[[Файл:DariaPicture8. 5)png|400px|поиск 13(рис. 6)]]

Глубина нашего Для того, чтобы сохранить структуру tango-дерева lognИз каждой вершины выходит <= 2 реберВ общем случае одно жирное(splay-дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, другое неткогда жирные ребра изменяются в результате поиска. Все наше дерево можно разбить на жирные После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (рискоторый становится нижней частью).7)

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

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

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

ПоискПоиск ключа xИщем # Так как мы знаем интервал значений <tex>[l', r']</tex> вершины <tex>t</tex> в корне tango-дерева – splay-деревеее правом поддереве <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>.Поиск в splay-дереве(синем) дереве = высота # Проведем тонкое ребро от количества вершин (количество вершин - длина жирного пути = log n) = log log nвершины <tex>t</tex> к дереву <tex>D</tex>.

Поиск во всем дереве Таким образом, перестройка = <tex>(3 \cdot split + 3 \cdot merge) \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-дереве.

Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам. //Теперь мы изменяем жирное ребро, т е хотим отрезать 13 и подвесить 10 9//Отрезать 13 легко, ====Пример====//- split по ключу, теперь х в корне, и отрезаем правое дерево[[Файл:DariaPicture9.png|1200px|// Как обратно вставить 9 10Merge в splay-дереве.T1<T2 сливаем в T, T1 – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем Т2.]]

Разрезаем жирные ребра==Источники информации==*[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. Splitug/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]вырезаем этот диапазон с помощью двух сплитов по rmin и по rmax*[http://john2.В новое независимое дерево ставим красный указатель на вершинуpoly.edu/papers/sicomp05/paper.pdf Erik D.Старый красный указатель вел в деревоDemaine, Dion Harmon, John Iacono, которое надо слить с его предком.Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершинеMihai Patrascu, от которой пошли.Dynamic Optimality—Almost]