170
правок
Изменения
м
Нет описания правки
{{Определение
|definition=Множество точек называется '''древесным''' (англ. ''aboral''), если выполняется следующее свойство:
на сторонах любого невырожденного(площадь прямоугольника больше нуля) прямоугольника, построенного на двух точках, есть еще хотя бы одна точка.
}}
Предположим, что это не удалось сделать.
У нас есть вершина <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>
{{Определение
|definition='''Жирное ребро'''(англ. ''Prefered edge'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i) \geqslant \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
{{Определение
|definition='''Жирный путь'''(англ. ''Prefered path'') {{---}} путь, состоящий из жирный ребер.
}}
Таким образом, все наши ключи организуют иерархичную структуру {{---}} Tango-дерево.
Каждый жирный путь {{---}} splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына).
Глубина tango-дерева <tex>\log n</tex>.
Начинаем с поиска в жирном пути корня tango-дерева {{---}} splay-дереве.
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелка) и осуществим поиск в новом жирном пути(splay-дереве).
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = <tex>\log n</tex>) = <tex>\log \log n</tex>.
Поиск во всем дереве = <tex>(\log \log n) \cdot </tex> число проходов по нежирному ребру.
# Так как мы знаем интервал значений <tex>[l', r']</tex> вершины <tex>t</tex> в ее правом поддереве <tex>D</tex>, сделаем по концам отрезка две операции <tex>split</tex>. Теперь мы можем отрезать поддерево <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>.
==Ссылки==
*[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]
