1632
правки
Изменения
м
На на сторонах любого невырожденного(площадь прямоугольника больше нуля) прямоугольника, построенного на двух точках, как на противоположных вершинах (левая нижняя-правая верхняя или левая верхняя-правая нижняя), есть еще хотя бы одна точка.
Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
Для ключа <tex>x_{j}</tex> рассмотрим ключи Рассмотрим запросы <tex>x_{i} : x_{I} = x_{j}, i = 0..j - 1</tex>
Из каждой вершины создадим вспомогательную ссылку на корень splay-дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.
Время Общее время работы дерева <tex>(M + K) \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер, <tex>M</tex> {{---}} число запросов.
rollbackEdits.php mass rollback
'''Tango-дерево''' {{---}} online бинарное дерево поиска с временем работы <tex> O(\log \log N) </tex>, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu Михаи Патраску в 2004 году. Лучшая Это лучшая известная реализация на данный момент.
Время работы tango-дерева <tex>O(OPT OPT_{dyn } \cdot \log \log n)</tex>
==Динамическая оптимальность==
Рассмотрим для начала понятия online/offline динамически/статически оптимального дерева поиска.
В '''статическом''' бинарном дереве поиска не происходит поворотов вокруг ребер. Его оптимальность зависит только от начального положения дерева. Это отличает его от '''динамического''' дерева, в котором повороты вокруг ребер разрешены.
'''Offline дерево''' поиска получает все запросы сразу и может использовать дополнительную память и вычисления для нахождения наиболее оптимальной последовательности обработки запросов. Стоимость работы дерева поиска для заданной последовательности ключей это стоимость доступа к каждому ключу и модификации дерева, и она не зависит от того, сколько времени мы потратили, чтобы найти оптимальную последовательность.
'''Online дерево''' поиска получает следующий запрос, только когда ответит на текущий, соответственно время работы пропорциональное стоимости исполнения запросов. Таким является splay-дерево.
{{Определение
|definition=Пусть <tex>OPT(S)</tex> {{---}} оптимальное время работы бинарного дерева поиска для последовательности запросов <tex>S</tex>.
Если стоимость запросов в бинарном дереве поиска {{---}} <tex>O(n + OPT(S))</tex> для всей ключей от <tex> 1 </tex> до <tex> n </tex>, то дерево называется '''динамически оптимальным'''.
}}
Это свойство трудно показать. Неизвестно, есть ли какое-то динамически оптимальное online бинарное дерево поиска, и также неизвестно полиномиальное время для вычисления <tex>OPT(S)</tex> с точностью до константы.
Обозначим время работы динамически оптимального дерева <tex>O(OPT_{dyn})</tex>, где <tex>OPT_{dyn} = n + OPT(S)</tex>.
{{Гипотеза
|statement=[http://neerc.ifmo.ru/wiki/index.php?title=[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''), если выполняется следующее свойство:
}}
{{Определение
|definition='''Фазовая диаграмма (диаграмма состояния) работы с деревом — ''' {{---}} графическое отображение состояния дерева, при котором координата точки <tex>(x_{i}, i)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени<tex>i</tex>.
}}
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.
Рассмотрим наше множество точек.
Построим из них [[Декартово дерево | декартово(!) дерево]], где ключом будет ключ, а вспомогательным ключом {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>. Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
[[Файл:DariaPicture3.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>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.
Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
}}
<tex>OPT(x) = \Omega(f) </tex>
Если что-то работает за ''<tex>O(f \cdot g)''</tex>, значит это работает не более, чем в ''<tex>g'' </tex> раз хуже.
Рассмотрим запросы.
То есть <tex>OPT(x) = \Omega(M + MP / 2)</tex>
==Вторая нижняя оценка Уилбера (англ. ''Wilber'') ==
Для каждого запроса <tex>xx_{j}</tex> вычислим число Уилбера.
Пусть <tex>a_{i} a < x_{j} < b_{i}b</tex>, где <tex>a_{i}a</tex> и <tex>b_{i}b</tex> {{---}} левая и правая границы на момент <tex>i</tex>.На момент времени <tex> i = 0 : a = -\infty, b = +\infty</tex>.Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i} : \{x_{ij} > a, < x_{i} < x a\} </tex>. Аналогично правую.В каждый момент времени позиция <tex>a_{i}a</tex> может увеличиваться, <tex>b_b</tex> уменьшаться.Рано или поздно, наши границы <tex>a</tex> и <tex>b</tex> встретятся в <tex>x_{i} = x_{j}</tex> уменьшаться.
Напишем <tex>r</tex>, если изменяется правая граница <tex>b_{i}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> множество попарно независимых прямоугольников.
[[Файл:DariaPicture11DariaPicture12.png|300px]]
{{Определение
|definition='''Жирное ребро'''(англ. ''Prefered edge'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
{{Теорема
|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>
Организуем их в полное двоичное [http://neerc.ifmo.ru/wiki/index.php?title=Дерево_поиска[Дерево поиска,_наивная_реализация наивная реализация | сбалансированное дерево]].Если <tex>n</tex> {{---}} не степень двойки, то на последний уровень будет заполнен не до конца.
Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i) \geqslant \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слеваот нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
===Построение===
Рассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути.
{{Определение
|definition='''Жирный путь'''(англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирный жирных ребер.
}}
]]
Каждый из этих жирных путей организуем в свое splay-дерево. Splay-дерево может быть построено как угодно. Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка). Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.
[[Файл:DariaPicture8.png|600px|
Таким образом, все наши ключи организуют иерархичную структуру {{---}} Tango-дерево.
Каждый жирный путь {{---}} splay-дерево, и каждое их них каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)вершины по нежирному ребру.
Глубина tango-дерева <tex>\log n</tex>.
Операций первого становления ребра жирным {{---}} ''<tex>O(\log n)''</tex>, это дает несущественный вклад в асимптотику.
===Поиск===
Начинаем с поиска в жирном пути корня tango-дерева {{---}} splay-дереве.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелкав tango-дереве) и осуществим поиск в новом жирном пути(splay-дереве).
Поиск в splay-дереве(синемсинее дерево в 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>minChild</tex> {{---}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{---}} максимальное значение в поддереве.
Во-вторых, нам понадобятся операции [http://neerc.ifmo.ru/wiki/index.php?title=[Splay-дерево | split]] и [http://neerc.ifmo.ru/wiki/index.php?title=[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>[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>.
Таким образом,
перестройка = <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-дереве.
]]
Операции вставки и удаления в 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]
[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]
