Изменения
Нет описания правки
'''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-дереве.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелкав 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]
[[Категория: - Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]
