Tango-дерево

Танго дерево Поиск Перестройка дерева

Динамическая оптимальность

Гипотеза:

Splay деревья обладают динамической оптимальностью. То есть если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных. Время работы splay дерева [math]O(OPT dyn)[/math]

Модель оптимального дерева

Рассмотрим ключи [math]1..n[/math] и запросы [math]x_{1}..x_{n}[/math], где [math]x_{i} \in \{1..n\}[/math] – ключ, к которому мы обращаемся.

Утверждение:

Существует гипотетически оптимальное дерево, которое на каждый запрос делает следующие вещи идет от корня до [math]x_{i}[/math] делает какое-то количество поворотов

Оценка снизу на динамический оптимум

Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска

Рассмотрим систему координат ключ -- время. Поставим точки, которые соответствуют обращению по данному ключу в определенное время.

Множество точек определяет, что происходило с деревом.

Определение:

Множество точек называется древесным (aboral), если выполняется следующее свойство: возьмем произвольный невырожденный прямоугольник(площадь прямоугольника больше нуля) с углами в наших точках.

Утверждение:

Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике с вершинами в наших точках есть еще хотя бы одна точка, отличная от точек, на которых его построили.

Теорема:

Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.

Доказательство:

[math]\triangleright[/math]

1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности. Пусть мы обращались к какому-то ключу [math]x[/math] в [math]i[/math]-ом запросе и к какому-то ключу [math]y[/math] в [math]j[/math]-ом запросе. Рассмотрим этот прямоугольник. На момент [math]i[/math]-го запроса рассмотрим в дереве поиска наименьшего общего предка [math]x[/math] и [math]y[/math] -- вершину [math]t[/math]. Если [math]t != x[/math], то все хорошо, значит в дереве поиска она находится между [math]x[/math] и [math]y[/math], поэтому мы к нему обращались в то время, когда шли к [math]x[/math], значит есть точка на стороне нашего многоугольника. Если [math]t = x[/math], то есть [math]x[/math] -- предок [math]y[/math] в момент [math]i[/math]-го запроса, тогда рассмотрим момент [math]j[/math]-го запроса, когда мы обращались к [math]y[/math]. Найдем в дереве поиска наименьшего общего предка [math]t[/math] вершин [math]x[/math] и [math]y[/math] на момент [math]j[/math]-го запроса. Если [math]t != y[/math], тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника. Если [math]t = y[/math], то есть [math]y[/math] - предок [math]x[/math] в момент [math]j[/math]-го запроса, Значит [math]y[/math] «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от [math]y[/math] к родителю. То есть во время [math]i[/math]-го запроса [math]y[/math] был в поддереве [math]x[/math], а во время [math]j[/math]-го запроса [math]x[/math] в поддереве [math]y[/math], значит где-то между этими моментами выполнялся поворот вокруг ребра от [math]y[/math] к родителю, и мы обращались к [math]y[/math], следовательно есть точка на правой стороне нашего прямоугольника. (рисунок надо?) 2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска. Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне. Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам. Рассмотрим наше множество точек. Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом – время, когда мы следующий раз обратимся к вершине, то есть для каждого [math]x[/math] найдем минимальный [math]y[/math] такой, что существует точка [math](x, y)[/math] построение декартова дерева Приоритет [math]y[/math] будет меняться по мере того, как мы будет симулировать работу с деревом поиска. Рассмотрим общий случай Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева. Обойдем эти точки. После этого мы должны перестроить наше дерево, изменив приоритеты. Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами. Почему? Предположим, что это не удалось сделать. У нас есть вершина [math]x[/math], у которой есть правый сын [math]y[/math], и приоритет [math]x[/math] больше чем у [math]y[/math], их надо поменять, то есть дотронуться до вершины [math]y[/math], чего мы делать не хотели в этой строке. Но тогда рассмотрим прямоугольник(мы обращались к [math]x[/math]) А когда-то мы обратимся к [math]y[/math] Если есть точка на левой стороне, то к [math]x[/math] мы обратимся раньше, чем к [math]y[/math] следовательно неверно, что приоритет [math]x[/math] больше чем приоритет [math]y[/math] На левой стороне точек нет. Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у [math]x[/math], но меньше [math]y[/math], но тогда она должна быть нашим правым сыном, а не вершина [math]y[/math]. Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к [math]y[/math]. Если на верхней стороне есть точка [math]z[/math] с ключом меньше [math]y[/math], мы будем обращаться к ней тогда же, когда и к [math]y[/math], значит мы может перейти к прямоугольнику, построенному на точках [math]x[/math] и [math]z[/math]. Когда таких точек (как [math]z[/math]) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию. Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.

[math]\triangleleft[/math]

Таким образом, мы получили какую-то offline оптимальность.

Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно количество точек на диаграмме.

Получим нижнюю оценку на оптимум. [math]OPT = omega(f) [/math] Если что-то работает за [math]O(f * g)[/math], значит это работает не более, чем в [math]g[/math] раз хуже.

Рассмотрим запросы.

Покроем их независимыми прямоугольниками.

Прямоугольники независимы, если угол одного не лежит внутри другого.

Можно показать, что [math]OPT \gt = M[/math](число запросов) + максимальное число независимых прямоугольников * 1/2

Вторая нижняя оценка Уилберра (Wilber)

Для каждого запроса [math]x[/math] вычислим число Уилберра.

Для ключа [math]x_[j][/math] рассмотрим ключи [math]x_{i} : x_{I} = x_{j}, i = 0..j - 1[/math]

Пусть [math]a_{i} \lt x_{j} \lt b_{i}[/math], где [math]a_{i}[/math] и [math]b_{i}[/math] -- левая и правая границы на момент i. Будем передвигать левую границу каждый раз, когда встречаем число [math]x_{i} : x_{i} \gt a, x_{i} \lt x [/math]. Аналогично правую. В каждый момент времени позиция [math]a_{i}[/math] может увеличиваться, [math]b_{i}[/math] уменьшаться.

Напишем [math]r[/math], если изменяется правая граница [math]b_{i}[/math] и [math]l[/math] - если левая.

Числом Уилберра [math]ch(i)[/math] называется количество смен [math]r[/math] на [math]l[/math] и обратно.

Получаем следующую оценку

[math]OPT \gt = \sum\limits_{i \in [1, n]} 1 + ch(i)[/math]

Теорема:

Рассмотрим [math]n[/math] ключей и [math]m[/math] запросов запросы [math]x_{1} .. x_{m}[/math] Организуем их в полное двоичное сбалансированное дерево. Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве. Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро). Утверждается, что [math]\sum\limits_{i \in [1, n]} ch(i)[/math] >= [math]\sum\limits_{i \in [1, n]}[/math] изменения числа жирных ребер. То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.

Tango-деревья

Определение:

Танго дерево - online бинарное дерево поиска с временем работы [math] O(log log N) [/math], которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году. Лучшая известная реализация на данный момент.

Время работы tango дерева [math]O(OPT dyn * log log n)[/math]

Построение

Определение:

Жирное ребро(Prefered Path) - ребро, соединяющее вершину с ее последним посещенным ребенком.

Рассмотрим бинарное дерево поиска.

Изначально сделаем все левые ребра жирными.

Разобьем наше дерево на жирные пути.

Каждый из этих жирных путей организуем в свое splay-дерево.

Из каждой вершины создадим вспомогательную ссылку на корень splay дерева, соответствующего жирному пути, в котором лежит тот ее ребенок, в который ведет из нее нежирное ребро.

Таким образом, все наши ключи организуют иерархичную структуру -- Tango дерево.

Каждый жирный путь -- splay дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына).

Глубина tango дерева [math]log n[/math].

Время работы (M + число изменений жирных ребер) *[math] log log n[/math]

Операций первого становления ребра жирным -- O(log n), это дает несущественный вклад в асимптотику.

Поиск

Поиск элемента в [math]tango[/math] дереве схож с поиском в обычном дереве поиска.

Начинаем с поиска в жирном пути корня [math]tango[/math] дерева –- [math]splay[/math] дереве.

Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке(красная стрелка) и осуществим поиск в новом жирном пути([math]splay[/math] дереве).

Поиск в [math]splay[/math] дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = [math]log n[/math]) = [math]log log n[/math].

Поиск во всем дереве = [math](log log n)[/math] * число проходов по нежирному ребру.

Пример

Перестройка дерева

Для того, чтобы сохранить структуру [math]tango[/math] дерева ([math]splay[/math] дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, когда жирные ребра изменяются в результате поиска. После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).

Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: [math]minChild[/math] -- минимальное значение в поддереве текущей вершины, [math]maxChild[/math] -- максимальное значение в поддереве.

Во-вторых, нам понадобятся операции split и merge, которые работают за [math]O(log k)[/math], где [math]k[/math] - число узлов в [math]splay[/math] дереве.

Пусть для того, чтобы найти вершину [math]x[/math], которая находится в дереве [math]F[/math], мы прошли по тонкому ребру из вершины [math]t[/math], находящейся в дереве [math]A[/math]. Значит, нам нужно объединить деревья [math]A[/math] и [math]F[/math] и вырезать из дерева [math]A[/math] подддерево [math]D[/math], в которое ведет жирное ребро из вершины [math]t[/math].

Пусть поддерево [math]D[/math] -- правое. Для левого аналогично.

1. Так как мы знаем интервал значений [math][l', r'][/math] вершины [math]t[/math] в ее правом поддереве [math]D[/math], сделаем по концам отрезка две операции [math]split[/math]. Теперь мы можем отрезать поддерево [math]D[/math].
2. Все ключи дерева [math]F[/math] меньше [math]t[/math](так как бинарное дерево поиска), поэтому выполним операцию [math]split[/math] по максимальному значению [math]m[/math], меньшему [math]t[/math].
3. Выполним операцию merge деревьев [math]F[/math] и [math]H[/math].
4. Выполним операцию merge деревьев [math]FH[/math] и [math]G[/math].
5. Выполним операцию merge деревьев [math]FGH[/math] и [math]E[/math].
6. Проведем тонкое ребро от вершины [math]t[/math] к дереву [math]D[/math].

Таким образом, перестройка = [math]3 * split + 3 * merge[/math], каждый из них за [math]log log n = (O(1) + 3*O(log log n) + 3*O(log log n))[/math] * число изменений жирного ребра.

Пример

Ссылки

• Дополнительные главы алгоритмов, Tango-деревья