Изменения
Нет описания правки
'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu Михаи Патраску в 2004 году.
Это лучшая известная реализация на данный момент.
Время работы tango-дерева <tex>O(OPT_{dyn} \cdot \log \log n)</tex>
==Динамическая оптимальность==
Рассмотрим для начала понятия online/offline динкамическидинамически/статически оптмального оптимального дерева поиска.
{{Определение
|definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирный жирных ребер.
}}
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в 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]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
