Изменения

Перейти к: навигация, поиск

Tango-дерево

1369 байт добавлено, 17:23, 29 мая 2015
Нет описания правки
'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu Михаи Патраску в 2004 году.
Это лучшая известная реализация на данный момент.
Время работы tango-дерева <tex>O(OPT OPT_{dyn } \cdot \log \log n)</tex>
==Динамическая оптимальность==
Рассмотрим для начала понятия online/offline динкамическидинамически/статически оптмального оптимального дерева поиска.
|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>.
}}
 
{{Гипотеза
{{Определение
|definition='''Фазовая диаграмма (диаграмма состояния) работы с деревом ''' {{---}} графическое отображение состояния дерева, при котором координата точки <tex>(x_{i}, i)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени <tex>i</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(ij)</tex> множество попарно независимых прямоугольников.
[[Файл:DariaPicture11DariaPicture12.png|300px]]
{{Определение
Организуем их в полное двоичное [[Дерево поиска, наивная реализация | сбалансированное дерево]].
Если <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-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.
Из каждой вершины создадим вспомогательную ссылку на корень splay-дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.
[[Файл:DariaPicture8.png|600px|
Таким образом, все наши ключи организуют иерархичную структуру {{---}} Tango-дерево.
Каждый жирный путь {{---}} splay-дерево, и каждое их них каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит ее второй сын (при этом указатель ставится на само дерево, а не на сына)вершины по нежирному ребру.
Глубина tango-дерева <tex>\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|400px|
]]
[[Файл:DariaPicture5.png|400px|
]]
[[Файл:DariaPicture6.png|400px|
]]
 
'''Соответствие tango-дерева текущему бинарному дереву поиска'''
[[Файл:DariaPicture4DariaPicture14.png|300px400px|
]]
[[Файл:DariaPicture5DariaPicture13.png|300px400px|
]]
[[Файл:DariaPicture6DariaPicture8.png|300px400px|
]]
]]
 Операции вставки и удаления в tango-дереве не поддерживаются. ==СсылкиИсточники информации==
*[http://www.lektorium.tv/lecture/14247 А.С.Станкевич, Дополнительные главы алгоритмов, Tango-деревья]
*[http://erikdemaine.org/theses/dharmon.pdf Dion Harmon, New Bounds on Optimal Binary Search Trees]
*[http://john2.poly.edu/papers/sicomp05/paper.pdf Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu, Dynamic Optimality—Almost]
[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]
Анонимный участник

Навигация