Изменения

Танго '''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Это лучшая известная реализация на данный момент. Время работы tango-дерева <tex>O(OPT_{dyn} \cdot \log \log n)</tex>==Динамическая оптимальность==ПоискРассмотрим для начала понятия online/offline динамически/статически оптимального дерева поиска.Перестройка  В '''статическом''' бинарном дереве поиска не происходит поворотов вокруг ребер. Его оптимальность зависит только от начального положения дерева. Это отличает его от '''динамического''' дерева, в котором повороты вокруг ребер разрешены.

==Динамическая оптимальность=='''Offline дерево''' поиска получает все запросы сразу и может использовать дополнительную память и вычисления для нахождения наиболее оптимальной последовательности обработки запросов. Стоимость работы дерева поиска для заданной последовательности ключей это стоимость доступа к каждому ключу и модификации дерева, и она не зависит от того, сколько времени мы потратили, чтобы найти оптимальную последовательность. '''Online дерево''' поиска получает следующий запрос, только когда ответит на текущий, соответственно время работы пропорциональное стоимости исполнения запросов. Таким является splay-дерево.  {{Определение |definition=Динамическая оптимальность Пусть <tex>OPT(S)</tex> {{---}} оптимальное время работы бинарного дерева поиска для последовательности запросов <tex>S</tex>. Если стоимость запросов в бинарном дереве поиска {{---}} <tex>O(n + OPT(Dynamic OptS))</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|400pxthumb|thumbleft|right400px|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>, значит есть точка на стороне нашего многоугольника.

Если <tex>[[Файл:DariaPicture2.png|thumb|300px| t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>{{---}} наименьший общий предок х</tex> и <tex>у</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.(Рис.2) ]]Если <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>-го запроса,Значит <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>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>уy</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.  Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны. 

 Таким образом, мы получили какую-то ''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(ij)</tex>Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(j)</tex>множество попарно независимых прямоугольников. [[Файл:DariaPicture12.png|300px]]

Док{{Определение |definition='''Жирное ребро''' (англ. ''Prefered edge'') {{-во упр--}} ребро, соединяющее вершину с ее последним посещенным ребенком.}}

Следствие {{Теорема|statement=Рассмотрим <tex>n </tex> ключей и <tex>m </tex> запросов запросы x1 <tex>x_{1} .. xmОрганизуем их в полное двоичное сбалансированное дерево.(см рисунок)Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!тамДля каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).x_{m}</tex>

УтверждаетсяОрганизуем их в полное двоичное [[Дерево поиска, что сумма по всем i (ch(i)) наивная реализация | сбалансированное дерево]].Если <tex>= сумма по i изменения числа жирных реберТо есть если мы улучшили правую границу(мы искали чтоn</tex> {{---то справа), а потом улучшили левую(искали слева)}} не степень двойки, значит где-то по пути мы прошли туда-обратно и сменили жирное реброна последний уровень будет заполнен не до конца.

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

Пусть изначально все левые ребра были жирными.Операций первого становления ребра жирным OТо есть если мы улучшили правую границу (мы искали что-то справа), а потом улучшили левую (nискали слева от нас) – дают не существенный вклад в асимптотику, значит где-то по пути мы прошли туда-обратно и сменили жирное ребро. }}

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

(рисРассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути. 8)

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

ПоискПоиск ключа xИщем Каждый из этих жирных путей организуем в корне tango-дерева – свое splay-дереведерево.Если не нашли, значит надо идти по нежирному ребру.Пойдем по нему(красная стрелка) и ищем в новом деревеSplay-дерево может быть построено как угодно.Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = log n) = log log n

Поиск во всем Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве = поиска (log log nпри этом ссылка ставится на само дерево, а не на ребенка) * число проходов по нежирному ребру.

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

Но у нас Т1 не меньше Т2[[Файл: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) \cdot </tex> число проходов по ключу, по которому мы искалинежирному ребру.И вставим наше поддерево ====Пример===='''Изменение жирных ребер в жирный путьбинарном дереве поиска''' [[Файл:DariaPicture4.png|400px|]][[Файл:DariaPicture5.png|400px|Теперь надо отрезать старое жирное ребро]][[Файл:DariaPicture6.png|400px|]] Закончили в какой'''Соответствие tango-то вершинедерева текущему бинарному дереву поиска''' [[Файл:DariaPicture14.png|400px|]][[Файл:DariaPicture13.png|400px|]][[Файл:DariaPicture8.png|400px|]] ===Перестройка дерева=== Для того, лежащей в жирном чтобы сохранить структуру tango-дерева (splay-дерево соответствует текущему жирному пути.Надо посмотреть), мы должны обновлять его каждый раз, когда жирные ребра изменяются в какую сторону вело жирное реброрезультате поиска.Оно вело туда, куда мы не шлиПосле изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).Мы знаемВо-первых, что нужно вырезать из мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{---}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{---}} максимальное значение в поддереве. Во-вторых, нам понадобятся операции [[Splay-дерево | split]] и [[Splay-дерево | merge]], которые больше тойработают за <tex>O(\log k)</tex>, где <tex>k</tex> {{---}} число узлов в которой мы закончили<tex>splay</tex>- дереве. Пусть для того, но меньше того ключачтобы найти вершину <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>. Пусть поддерево <tex>D</tex> {{---}} правое. Для левого аналогично.Мы хотим отрезать все ключи# Так как мы знаем интервал значений <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> к дереву <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-дереве.И режем по минимальному и максимальному значениям в этом поддереве ====Пример====[[Файл:DariaPicture9.png|1200px|]] 

Разрезаем жирные ребра==Источники информации==*[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]