Изменения

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

==Динамическая оптимальность=={{Определение |definition=Динамическая оптимальность Пусть <tex>OPT(Dynamic OptS)</tex> {{---}} оптимальное время работы бинарного дерева поиска для последовательности запросов <tex>S</tex>. Если стоимость запросов в бинарном дереве поиска {{---}} <tex>O(n + 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|]]

Изначально сделаем все левые ребра жирнымиКаждый из этих жирных путей организуем в свое 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://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] [[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]