1632
правки
Изменения
м
Танго '''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>.
Время работы tango-дерева <tex>O(OPT dyn * log log n)</tex>
Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника. [[Файл:DariaPicture2.png|400pxthumb|300px|t {{--- }} наименьший общий предок х и у
(рисунок надо?) '''2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.'''
Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
Рассмотрим запрос То есть <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>r</tex>, если изменяется правая граница <tex>b</tex> и <tex>xl</tex> {{---}} если левая.
Можно показать, что из этой оценки выходит следующая оценка{{Определение|definition='''Числом Уилбера''' <tex>ch(j)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.}}
Напишем Получаем следующую оценку <tex>rOPT \geqslant \sum\limits_{j \in [1, n]} 1 + ch(j)</tex>Это можно вывести из предыдущей оценки, если меняется правая граница и построив соответствующее <tex>lch(j)</tex> - если леваямножество попарно независимых прямоугольников.
Назовем <tex>ch(i)</tex> количество смен <tex>r</tex> на <tex>l</tex> и обратно[[Файл:DariaPicture12.png|300px]]
<tex>OPT >{{Определение |definition= \sum\limits_'''Жирное ребро''' (англ. ''Prefered edge'') {{i \in [1---}} ребро, n]соединяющее вершину с ее последним посещенным ребенком.}} 1 + ch(i)</tex>
{{Определение
|definition=""Танго дерево"" - online бинарное дерево поиска с временем работы <tex> O(log log N) </tex>, создателями которого были Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.
Лучшая известная реализация на данный момент.
}}
===Пример===
[[Файл:DariaPicture4.png|300px|
]]
[[Файл:DariaPicture5.png|300px|
]]
[[Файл:DariaPicture6.png|300px|
]]
Изначально сделаем все левые ребра жирными[[Файл:DariaPicture7.png|400px|]]
Из каждой вершины выходит <= 2 реберКаждый из этих жирных путей организуем в свое splay-дерево.В общем случае одно жирное, другое нетSplay-дерево может быть построено как угодно.
Разобьем наше Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево , а не на жирные путиребенка).
[[Файл:DariaPicture7Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.png|400px|]]
Каждый из этих жирных путей организуем в свое splay-дерево.
Из каждой вершины создадим вспомогательную ссылку на корень splay-дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро. [[Файл:DariaPicture8.png|400px600px|
//Операций первого становления ребра жирным Глубина tango-дерева <tex>O(\log n)</tex> – дают несущественный вклад в асимптотику.
Глубина Общее время работы дерева <tex>(M + K) \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер, <tex>M</tex> {{---}} число запросов.
Время работы (M + число изменений жирных ребер) *Операций первого становления ребра жирным {{---}} <tex> log O(\log n)</tex>, это дает несущественный вклад в асимптотику.
Ищем Начинаем с поиска в корне жирном пути корня tango-дерева – {{---}} splay-дереве.
Пойдем по немуПоиск в splay-дереве (красная стрелка) и ищем синее дерево в новом splay-дереве) работает за высоту от количества вершин (количество вершин {{---}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <tex>\log \log n</tex>.
Поиск во всем ====Пример===='''Изменение жирных ребер в бинарном дереве = <tex>(log log n)</tex> * число проходов по нежирному ребру.поиска'''
===Перестройка дерева===[[Файл:DariaPicture4.png|400px|]][[Файл:DariaPicture5.png|400px|]][[Файл:DariaPicture6.png|400px|]]
Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам. '''Соответствие tango-дерева текущему бинарному дереву поиска'''
//Теперь мы изменяем жирное ребро, т е хотим отрезать 13 и подвесить 10 9[[Файл:DariaPicture14.png|400px|//Отрезать 13 легко, ]]//- split по ключу, теперь х в корне, и отрезаем правое дерево[[Файл:DariaPicture13.png|400px|// Как обратно вставить 9 10]]Merge в splay-дереве[[Файл:DariaPicture8.png|400px|<tex>T1<T2</tex> сливаем в <tex>T, T1</tex> – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем <tex>Т2</tex>.]]
Но у нас <tex>T1</tex> не меньше<tex> T2</tex>===Перестройка дерева===
Посмотрим на общий случайДля того, чтобы сохранить структуру 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>. Теперь мы может наше splay-можем отрезать поддерево <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-дереве.
Теперь надо отрезать старое жирное ребро.
Закончили в какой-то вершине, лежащей в жирном пути. Надо посмотреть, в какую сторону вело жирное ребро. Оно вело туда, куда мы не шли. Мы знаем, что нужно вырезать из нашего дерева вершины, которые больше той, в которой мы закончили, но меньше того ключа, из которого мы последний раз шли не в ту сторону, в которую мы сейчас идем не по жирному ребру. Нас интересует ключ, который больше нашего, но который выше нас. Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей? Но это дерево примитивное, оно является полным двоичным. В нем можем предподсчитать для каждой вершины минимум и максимум. Значит, мы знаем интервал значений вершин его правого поддерева. И режем по минимальному и максимальному значениям в этом поддереве. Итого Разрезаем жирные ребра, по которым мы не прошли. Берем ребро. Берем дерево. Берем вершину. Split. Она корень. Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,вырезаем этот диапазон с помощью двух сплитов по <tex>r_{min}</tex> и по <tex>r_{max}</tex>.В новое независимое дерево ставим красный указатель на вершину.====Пример====Старый красный указатель вел в дерево, которое надо слить с его предком[[Файл:DariaPicture9.png|1200px| Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли.]]
Перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра
rollbackEdits.php mass rollback
}}
{{Гипотеза
|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;
3) Запрос 4 : вершина 3 – вершина 4
]]
{{УтверждениеОпределение|statementdefinition=Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике '''Фазовая диаграмма (диаграмма состояния) работы с вершинами в наших точках есть еще хотя бы одна точкадеревом''' {{---}} графическое отображение состояния дерева, отличная от точекпри котором координата точки <tex>(x_{i}, на которых его построилиi)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени <tex>i</tex>.
}}
|proof=
'''1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности.'''
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.
Рассмотрим этот прямоугольник.
На момент <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>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>-го запроса.
Если <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>, следовательно есть точка на правой стороне нашего прямоугольника.
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.
Рассмотрим наше множество точек.
Построим из них [[Декартово дерево | декартово(!) дерево]], где ключом будет ключ, а вспомогательным ключом – {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <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>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>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию. Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
}}
Таким образом, мы получили какую-то ''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>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>
{{Теорема
|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> {{---}} число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слеваот нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
== Tango-деревья==
===Построение===
Рассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути.
{{Определение
|definition=Жирное ребро'''Жирный путь''' ("англ. ''Prefered Path"path'') {{- ребро--}} максимальный по включению путь, соединяющее вершину с ее последним посещенным ребенкомсостоящий из жирных ребер.
}}
]]
Таким образом, все наши ключи организуют иерархичную структуру {{-- -}} Tango -дерево.
Каждый жирный путь {{-- -}} splay-дерево, и каждое их них каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)вершины по нежирному ребру.
===Поиск===
Поиск ключа <tex>x</tex>элемента в tango-дереве схож с поиском в обычном дереве поиска.
Если текущий жирный путь не нашлисодержит искомый элемент, значит надо идти то сделаем переход по нежирному ребрувспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).
Поиск в splay-во всем дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = соответствует <tex>(\log \log n</tex>) = <tex>log log n\cdot </tex>число проходов по нежирному ребру.
Операции вставки и удаления в 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]
[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]
