Изменения

'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и 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>.

Гипотетическое время работы splay-дерева <tex>O(OPT OPT_{dyn})</tex>

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

|definition='''Фазовая диаграмма (диаграмма состояния) работы с деревом ''' {{---}} графическое отображение состояния дерева, при котором координата точки <tex>(x_{i}, i)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени <tex>i</tex>.

Построим из них [[http://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево Декартово дерево | декартово дерево]], где ключом будет ключ, а вспомогательным ключом {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>. Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.

Но тогда рассмотрим прямоугольник(мы обращались к <tex>x</tex>). А когда-то мы обратимся к <tex>y</tex>.

Для каждого запроса <tex>xx_{j}</tex> вычислим число Уилбера.

Для ключа <tex>x_{j}</tex> рассмотрим ключи Рассмотрим запросы <tex>x_{i} : \{x_{i} = x_{j}, i = 0..j - 1\}</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} : \{a x_{j} < x_{i} < xa\} </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> {{---}} не степень двойки, то на последний уровень будет заполнен не до конца.

То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слеваот нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.

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

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

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

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

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

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

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

'''Соответствие tango-дерева текущему бинарному дереву поиска''' [[Файл:DariaPicture4DariaPicture14.png|300px400px|

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

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

Во-вторых, нам понадобятся операции [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>F</tex> меньше <tex>t</tex>(так как бинарное дерево поиска), поэтому выполним операцию <tex>split</tex> по максимальному значению <tex>m</tex>, меньшему <tex>t</tex>.

 Операции вставки и удаления в tango-дереве не поддерживаются. ==СсылкиИсточники информации==

[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]