1632
правки
Изменения
м
}}
rollbackEdits.php mass rollback
'''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(j)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
}}
{{Определение
|definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирный жирных ребер.
}}
Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка).
Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерев дерева поиска.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).
Поиск в splay-дереве (синее дерево в splay-дереве) дереве работает за высоту от количества вершин (количество вершин {{---}}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <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]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
