Tango-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 135 промежуточных версий 7 участников)
Строка 1: Строка 1:
Танго дерево
+
'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.
Поиск
+
Это лучшая известная реализация на данный момент.
Перестройка дерева
 
  
 +
Время работы tango-дерева <tex>O(OPT_{dyn} \cdot \log \log n)</tex>
 +
==Динамическая оптимальность==
 +
Рассмотрим для начала понятия online/offline динамически/статически оптимального дерева поиска.
  
==Динамическая оптимальность==
+
 
{{Определение  
+
В '''статическом''' бинарном дереве поиска не происходит поворотов вокруг ребер. Его оптимальность зависит только от начального положения дерева. Это отличает его от '''динамического''' дерева, в котором повороты вокруг ребер разрешены.
Динамическая оптимальность(Dynamic Opt)
+
 
Если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.
+
 
 +
'''Offline дерево''' поиска получает все запросы сразу и может использовать дополнительную память и вычисления для нахождения наиболее оптимальной последовательности обработки запросов. Стоимость работы дерева поиска для заданной последовательности ключей это стоимость доступа к каждому ключу и модификации дерева, и она не зависит от того, сколько времени мы потратили, чтобы найти оптимальную последовательность.
 +
 
 +
'''Online дерево''' поиска получает следующий запрос, только когда ответит на текущий, соответственно время работы пропорциональное стоимости исполнения запросов. Таким является splay-дерево.
 +
 
 +
 
 +
{{Определение
 +
|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>.
  
 
{{Гипотеза
 
{{Гипотеза
Splay-деревья обладают динамической оптимальностью.
+
|statement=[[Splay-дерево | Splay-деревья]] обладают динамической оптимальностью.
То есть время работы splay-дерева O(OPT dyn)
+
То есть если мы разрешаем перестраивать деревья в процессе запроса, то splay-деревья не больше, чем в константу хуже оптимальных.
 +
Гипотетическое время работы splay-дерева <tex>O(OPT_{dyn})</tex>
 
}}
 
}}
  
===Модель оптимального дерева===
+
===Модель динамически оптимального дерева===
 +
 
 +
Рассмотрим ключи <tex>1..n</tex> и запросы <tex>x_{1}..x_{n}</tex>, где <tex>x_{i} \in \{1..n\}</tex> {{---}} ключ, к которому мы обращаемся.
  
Рассмотрим ключи 1..n и запросы x1..xn, где xi принадлежит {1..n} – ключ, к которому мы обращаемся.
+
{{Утверждение
 +
|statement=Существует гипотетически оптимальное дерево, которое на каждый запрос делает следующие вещи:
 +
# Идет от корня до <tex>x_{i}</tex>
 +
# Делает какое-то количество поворотов
 +
}}
  
Утверждение
+
===Оценка снизу на динамический оптимум===
Существует некоторое гипотетическое оптимальное дерево, которое на каждый запрос делает следующие вещи
 
- идет от корня до xi
 
- делает какие-то количество поворотов
 
  
Время работы tango-дерева O(OPT dyn * log log n)
+
====Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска====
  
Оценка снизу на динамический оптимум
+
Рассмотрим систему координат ключ {{---}} время.
 +
Поставим точки, которые соответствуют обращению по данному ключу в определенное время.
  
Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска
+
Множество точек определяет, что происходило с деревом.
 +
{{Определение
 +
|definition=Множество точек называется '''древесным''' (англ. ''aboral''), если выполняется следующее свойство:
 +
на сторонах любого невырожденного (площадь прямоугольника больше нуля) прямоугольника, построенного на двух точках, как на противоположных вершинах (левая нижняя-правая верхняя или левая верхняя-правая нижняя), есть еще хотя бы одна точка.
 +
}}
  
Рассмотрим оси ключи от времени
+
[[Файл:DariaPicture1.png|thumb|left|400px|
Поставим точки, которые соответствуют обращению по данному ключу в определенное время.
+
1) Запрос  вершины 3 : вершина 3;
  
Множество точек определяет, что происходило с деревом.
+
2) Запрос 2 : вершина 3 – вершина 1 – вершина 2;
Множество точек называется древесным (aboral), если выполняется следующее свойство:
 
возьмем произвольный невырожденный прямоугольник(площадь прямоугольника больше нуля) с углами в наших точках.
 
  
(рис. 1)
 
1) Запрос  вершины 3 : вершина 3
 
2) Запрос 2 : вершина 3 – вершина 1 – вершина 2
 
 
3) Запрос 4 : вершина 3 – вершина 4
 
3) Запрос 4 : вершина 3 – вершина 4
 +
]]
 +
 +
{{Определение
 +
|definition='''Фазовая диаграмма (диаграмма состояния) работы с деревом''' {{---}} графическое отображение состояния дерева, при котором координата точки <tex>(x_{i}, i)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени <tex>i</tex>.
 +
}}
  
Утверждение
+
{{Теорема
Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике с вершинами в наших точках есть еще хотя бы одна точка, отличная от точек, на которых его построили.
+
|statement=Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.
  
Теорема
+
|proof=
Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.
+
'''1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности.'''
  
Доказательство
+
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.
 +
Рассмотрим этот прямоугольник.
 +
На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x</tex> и <tex>y</tex> {{---}} вершину <tex>t</tex>.
 +
Если <tex>t  \ne x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>x</tex> и <tex>y</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>x</tex>, значит есть точка на стороне нашего многоугольника.
  
1) Фазовая диаграмма работы с деревом поиска обралает свойством древестности.
+
[[Файл:DariaPicture2.png|thumb|300px| t {{---}} наименьший общий предок х и у
 +
]]
 +
Если <tex>t = x</tex>, то есть <tex>x</tex> {{---}} предок <tex>y</tex> в момент <tex>i</tex>-го запроса,
 +
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
 +
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
  
Пусть мы обращались к какому-то ключу x в i-ом запросе и к какому-то ключу y в j-ом запросе.
+
Если <tex>t \ne y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
Рассмотрим этот прямоугольник.
+
Если <tex>t = y</tex>, то есть <tex>y</tex> {{---}} предок <tex>x</tex> в момент <tex>j</tex>-го запроса,
На момент i-го запроса рассмотрим в дереве поиска наименьшего общего предка x и y – вершину t.
+
Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.
Если t  != x, то все хорошо, значит в дереве поиска он находится между х и у, поэтому мы к нему обращались в то время, когда шли к х, значит есть точка на стороне нашего многоугольника.
 
(Рис.2)
 
  
Если t = x, то есть х - предок у в момент i-го запроса,
+
То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника.
тогда рассмотрим момент j-го запроса, когда мы обращались к y.
 
Найдем в дереве поиска наименьшего общего предка t вершин x и y на момент j-го запроса.
 
Если t != y, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
 
Если t = y, то есть y - предок x в момент j-го запроса,
 
Значит y «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от у к родителю.
 
То есть во время i-го запроса y был в поддереве х, а во время j-го запроса х в поддереве у, значит где-то между этими моментами выполнялся поворот вокруг ребра от у к родителю, и мы обращались к у, следовательно есть точка на правой стороне нашего прямоугольника
 
(рисунок надо?)
 
  
2) Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.
+
'''2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.'''
  
 
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
 
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
 
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.  
 
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.  
 
 
Рассмотрим наше множество точек.
 
Рассмотрим наше множество точек.
Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом время, когда мы следующий раз обратимся к вершине, то есть для каждого х  найдем минимальный у такой, что существует точка (х, у)
+
Построим из них [[Декартово дерево | декартово дерево]], где ключом будет ключ, а вспомогательным ключом {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>. Приоритет <tex>y</tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
  
(рис.3)
+
[[Файл:DariaPicture3.png|thumb|300px| Построение декартова дерева
??Декартово дерево становится такое
+
]]
  
y будет меняться по мере того, как мы будет симулировать работу с деревом поиска.
+
Рассмотрим общий случай
  
 
Рассмотрим общий случай
 
 
Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.
 
Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.
 
Обойдем эти точки.
 
Обойдем эти точки.
После этого мы должны перестроить наше дерево, изменив приоритеты
+
После этого мы должны перестроить наше дерево, изменив приоритеты.
Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами
+
Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами.
 
Почему?
 
Почему?
 
Предположим, что это не удалось сделать.  
 
Предположим, что это не удалось сделать.  
У нас есть вершина х,  у которой есть правый сын у, и приоритет у х больше чем у у, их надо поменять, то есть дотронуться до вершины у, чего мы делать не хотели в этой строке.
+
У нас есть вершина <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>
 +
На левой стороне точек нет.
 +
 
 +
Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.
  
Если есть точка на левой стороне, то к х мы обратимся раньше, чем к у следовательно неверно, что приоритет х больше чем приоритет у
+
Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к <tex>y</tex>.
На левой стороне точек нет
 
  
Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у х, но меньше у, но тогда она должна быть нашим правым сыном, а не вершина у.
+
Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.  
  
Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к y.
+
Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию. Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
  
Если на верхней стороне есть точка z с ключом меньше y, мы будем обращаться к ней тогда же, когда и к у, значит мы может перейти к прямоугольнику, построенному на точках x и z.
+
}}
Когда таких точек (как z) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это  противоречит исходному условию.
 
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны
 
  
Таким образом, мы получили какую-то offline оптимальность.
+
Таким образом, мы получили какую-то ''offline'' оптимальность.
  
Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно кол-во точек на диаграмме.  
+
Рассмотрим наши запросы, отметим их точками, тогда время работы оптимального динамического дерева равно количество точек на диаграмме.  
  
 
Получим нижнюю оценку на оптимум.
 
Получим нижнюю оценку на оптимум.
Оптимум = омега(f)
+
<tex>OPT(x) = \Omega(f) </tex>
Если что-то работает за O(f * g), значит это работает не более, чем в g раз хуже.
+
 
 +
Если что-то работает за <tex>O(f \cdot g)</tex>, значит это работает не более, чем в <tex>g</tex> раз хуже.
  
 
Рассмотрим запросы.
 
Рассмотрим запросы.
 
Покроем их независимыми прямоугольниками.
 
Покроем их независимыми прямоугольниками.
 
Прямоугольники независимы, если угол одного не лежит внутри другого.
 
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что оптимум(OPT) >= M(число запросов) +  максимальное число независимых прямоугольников * 1/2
 
Вторая нижняя оценка Уилберра (Wilber)
 
Рассмотрим запрос х
 
Пусть левая граница = -бесконечность, правая граница = +бесконечность
 
Идем от ключа x назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
 
И каждый раз, когда встречается значение больше, чем наше, но меньше правой границы, мы сдвигаем правую границу.
 
Аналогично с левой границей.
 
Когда-то рано или поздно наши границы встретятся в х
 
Можно показать, что из этой оценки выходит следующая оценка
 
Напишем r, если меняется правая граница и l  - если левая.
 
Назовем ch(i) количество смен r на l и обратно
 
  
Оптимум >= сумме по всем запросам(i) (1 + ch(i))
+
Можно показать, что <tex>OPT(x) \geqslant M +  MP / 2</tex>, где <tex>M</tex> {{---}} число запросов, <tex>MP</tex> {{---}} максимальное число независимых прямоугольников.
 +
 
 +
То есть <tex>OPT(x) =  \Omega(M + MP / 2)</tex>
 +
 
 +
==Вторая нижняя оценка Уилбера (Wilber) ==
 +
 
 +
Для каждого запроса <tex>x_{j}</tex> вычислим число Уилбера.
 +
 
 +
Рассмотрим запросы <tex>x_{i}, i = 0..j</tex>
 +
 
 +
Пусть <tex>a < x_{j} < b</tex>, где <tex>a</tex> и <tex>b</tex> {{---}}  левая и правая границы на момент <tex>i</tex>.
 +
На момент времени <tex> i = 0 : a = -\infty, b = +\infty</tex>.
 +
Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i}  : \{x_{j} < x_{i} < a\} </tex>. Аналогично правую.
 +
В каждый момент времени позиция <tex>a</tex> может увеличиваться, <tex>b</tex> уменьшаться.
 +
Рано или поздно, наши границы <tex>a</tex> и <tex>b</tex> встретятся в <tex>x_{i} = x_{j}</tex>
 +
 
 +
Напишем <tex>r</tex>, если изменяется правая граница <tex>b</tex> и <tex>l</tex>  {{---}} если левая.
 +
 
 +
{{Определение
 +
|definition='''Числом Уилбера''' <tex>ch(j)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
 +
}}
 +
 
 +
Получаем следующую оценку
 +
<tex>OPT \geqslant \sum\limits_{j \in [1, n]} 1 + ch(j)</tex>
 +
Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(j)</tex> множество попарно независимых прямоугольников.
 +
 
 +
[[Файл:DariaPicture12.png|300px]]
 +
 
 +
{{Определение
 +
|definition='''Жирное ребро''' (англ. ''Prefered edge'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов <tex>x_{1} .. x_{m}</tex>
 +
 
 +
Организуем их в полное двоичное [[Дерево поиска, наивная реализация | сбалансированное дерево]].
 +
Если <tex>n</tex> {{---}} не степень двойки, то на последний уровень будет заполнен не до конца.
 +
 
 +
Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.
 +
 
 +
Для каждой вершины будем запоминать жирное ребро.
 +
 
 +
Утверждается, что  <tex>\sum\limits_{i \in [1, n]} ch(i) \geqslant  \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
 +
 
 +
То есть если мы улучшили правую границу (мы искали что-то справа), а потом улучшили левую (искали слева от нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
 +
}}
 +
 
 +
== Tango-деревья==
 +
 
 +
===Построение===
 +
 
 +
Рассмотрим бинарное дерево поиска. Изначально сделаем все левые ребра жирными. Разобьем наше дерево на жирные пути.
 +
 
 +
{{Определение
 +
|definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирных ребер.
 +
}}
 +
 
 +
[[Файл:DariaPicture7.png|400px|
 +
]]
 +
 
 +
Каждый из этих жирных путей организуем в свое splay-дерево. Splay-дерево может быть построено как угодно.
 +
 
 +
Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка).
 +
 
 +
Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.
 +
 
 +
 
 +
[[Файл:DariaPicture8.png|600px|
 +
]]
 +
 
 +
Таким образом, все наши ключи организуют иерархичную структуру {{---}} Tango-дерево.
 +
 
 +
Каждый жирный путь  {{---}} splay-дерево, и каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит сын вершины по нежирному ребру.
 +
 
 +
Глубина tango-дерева <tex>\log n</tex>.
 +
 
 +
Общее время работы дерева <tex>(M + K) \cdot \log \log n</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер, <tex>M</tex> {{---}} число запросов.
 +
 
 +
Операций первого становления ребра жирным  {{---}} <tex>O(\log n)</tex>, это дает несущественный вклад в асимптотику.
 +
 
 +
===Поиск===
 +
 
 +
Поиск элемента в tango-дереве схож с поиском в обычном дереве поиска.
 +
 
 +
Начинаем с поиска в жирном пути корня tango-дерева {{---}} splay-дереве.
 +
 
 +
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).
  
Док-во упр
+
Поиск в splay-дереве (синее дерево в splay-дереве) работает за высоту от количества вершин (количество вершин {{---}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <tex>\log \log n</tex>.
  
Следствие
+
Поиск во всем дереве соответствует  <tex>(\log \log n) \cdot </tex> число проходов по нежирному ребру.
Рассмотрим n ключей и m запросов запросы x1 .. xm
 
Организуем их в полное двоичное сбалансированное дерево.
 
(см рисунок)
 
Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!там
 
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
 
  
Утверждается, что  сумма по всем i (ch(i)) >= сумма по i изменения числа жирных ребер
+
====Пример====
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
+
'''Изменение жирных ребер в бинарном дереве поиска'''
  
 +
[[Файл:DariaPicture4.png|400px|
 +
]]
 +
[[Файл:DariaPicture5.png|400px|
 +
]]
 +
[[Файл:DariaPicture6.png|400px|
 +
]]
  
Итак, tango-деревья
+
'''Соответствие tango-дерева текущему бинарному дереву поиска'''
  
Пример
+
[[Файл:DariaPicture14.png|400px|
поиск 5
+
]]
(рис. 4)
+
[[Файл:DariaPicture13.png|400px|
поиск 10
+
]]
(рис. 5)
+
[[Файл:DariaPicture8.png|400px|
поиск 13
+
]]
(рис. 6)
 
  
Пусть изначально все левые ребра были жирными.
+
===Перестройка дерева===
Операций первого становления ребра жирным O(n) – дают не существенный вклад в асимптотику.
 
  
Глубина нашего дерева logn
+
Для того, чтобы сохранить структуру tango-дерева (splay-дерево соответствует текущему жирному пути), мы должны обновлять его каждый раз, когда жирные ребра изменяются в результате поиска.
Из каждой вершины выходит <= 2 ребер
+
После изменения жирного ребра верхняя часть жирного пути отделяется от нижней части (которая становится самостоятельным жирным путем) и присоединяется к другому жирному пути (который становится нижней частью).  
В общем случае одно жирное, другое нет
 
Все наше дерево можно разбить на жирные пути  
 
(рис.7)
 
  
Каждый из этих жирных путей организуем в свое splay-дерево.
+
Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{---}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{---}} максимальное значение в поддереве.
Из каждой вершины будет выходить вспомогательная ссылка на корень splay-дерева, соответствующего жирному пути в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.
 
  
(рис. 8)
+
Во-вторых, нам понадобятся операции [[Splay-дерево | split]] и [[Splay-дерево | merge]], которые работают за <tex>O(\log k)</tex>, где <tex>k</tex> {{---}} число узлов в <tex>splay</tex>- дереве.
  
Таким образом, все наши ключи организуют иерархичную структуру.
+
Пусть для того, чтобы найти вершину <tex>x</tex>, которая находится в дереве <tex>F</tex>, мы прошли по тонкому ребру из вершины <tex>t</tex>, находящейся в дереве <tex>A</tex>.
Каждый жирный путь  - splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)
+
Значит, нам нужно объединить деревья <tex>A</tex> и <tex>F</tex> и вырезать из дерева <tex>A</tex> подддерево <tex>D</tex>, в которое ведет жирное ребро из вершины <tex>t</tex>.
  
Время работы (M + число изменений жирных ребер) * log log n
+
Пусть поддерево <tex>D</tex> {{---}} правое. Для левого аналогично.
  
Поиск
+
# Так как мы знаем интервал значений <tex>[l', r']</tex> вершины <tex>t</tex> в ее правом поддереве <tex>D</tex>, сделаем по концам отрезка две операции <tex>split</tex>. Теперь мы можем отрезать поддерево <tex>D</tex>.
Поиск ключа x
+
# Все ключи дерева <tex>F</tex> меньше <tex>t</tex> (так как бинарное дерево поиска), поэтому выполним операцию <tex>split</tex> по максимальному значению <tex>m</tex>, меньшему <tex>t</tex>.
Ищем в корне tango-дерева – splay-дереве.
+
# Выполним операцию merge деревьев <tex>F</tex> и <tex>H</tex>.
Если не нашли, значит надо идти по нежирному ребру.
+
# Выполним операцию merge деревьев <tex>FH</tex> и <tex>G</tex>.
Пойдем по нему(красная стрелка) и ищем в новом дереве.
+
# Выполним операцию merge деревьев <tex>FGH</tex> и <tex>E</tex>.
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = log n) = log log n
+
# Проведем тонкое ребро от вершины <tex>t</tex> к дереву <tex>D</tex>.
  
Поиск во всем дереве =  (log log n) * число проходов по нежирному ребру.
+
Таким образом,
 +
перестройка = <tex>(3 \cdot split + 3 \cdot merge) \cdot K = (O(1) + 3 \cdot O(\log \log n) + 3 \cdot O(\log \log n)) \cdot K</tex>  <tex>O(\log \log n \cdot OPT_{dyn}) </tex>, где <tex>K</tex> {{---}} число изменений жирного ребра, <tex>n</tex> {{---}} число вершин в tango-дереве.
  
Перестройка дерева
 
  
Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам.
+
====Пример====
//Теперь мы изменяем жирное ребро,  т е хотим отрезать 13 и подвесить 10 9
+
[[Файл:DariaPicture9.png|1200px|
//Отрезать 13 легко,
+
]]
//- split  по ключу,  теперь х в корне, и отрезаем правое дерево.
 
// Как обратно вставить 9 10
 
Merge в splay-дереве.
 
T1<T2 сливаем в T, T1 – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем Т2.
 
  
Но у нас Т1 не меньше Т2
 
Посмотрим на общий случай
 
Был жирный путь
 
Мы в нем что-то искали, не нашли, остановились в вершине, и хотим другое ее поддерево подклеить в жирный путь.
 
Заметим, что ее жирный путь с одной стороны в левом поддереве нашей вершины
 
С другой стороны в правом поддереве какого-то предка.
 
Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали.
 
И вставим наше поддерево в жирный путь.
 
Теперь надо отрезать старое жирное ребро.
 
Закончили в какой-то вершине, лежащей в жирном пути.
 
Надо посмотреть, в какую сторону вело жирное ребро.
 
Оно вело туда, куда мы не шли.
 
Мы знаем, что нужно вырезать из нашего дерева вершины, которые больше той, в которой мы закончили, но меньше того ключа, из которого мы последний раз шли не в ту сторону, в которую мы сейчас идем не по жирному ребру.
 
Нас интересует ключ, который больше нашего, но который выше нас.
 
Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей?.
 
Но это дерево примитивное, оно является полным двоичным.
 
В нем можем предподсчитать для каждой вершины минимум и максимум.
 
Значит, мы знаем интервал значений вершин его правого поддерева.
 
И режем по минимальному и максимальному значениям в этом поддереве.
 
  
Итого
+
Операции вставки и удаления в tango-дереве не поддерживаются.
  
Разрезаем жирные ребра, по которым мы не прошли.
+
==Источники информации==
Берем ребро. Берем дерево. Берем вершину. Split. Она корень.  
+
*[http://www.lektorium.tv/lecture/14247  А.С.Станкевич, Дополнительные главы алгоритмов, Tango-деревья]
Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,
+
*[http://erikdemaine.org/theses/dharmon.pdf Dion Harmon, New Bounds on Optimal Binary Search Trees]
вырезаем этот диапазон с помощью двух сплитов по rmin и по rmax.
+
*[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]
Старый красный указатель вел в дерево, которое надо слить с его предком.
+
*[https://www.cs.princeton.edu/courses/archive/fall08/cos521/tango.pdf Sanjeev Arora, Competitive analysis of data structures]
Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли.
+
*[http://john2.poly.edu/papers/sicomp05/paper.pdf Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu, Dynamic Optimality—Almost]
  
Перестройка = 3 * split + 3 * merge, каждый из них за loglogn = (O(1) + 3*O(log log n) + 3*O(log log n)) * число изменений жирного ребра
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Деревья поиска]]
 +
[[Категория:Структуры данных]]

Текущая версия на 19:23, 4 сентября 2022

Tango-дерево — online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Это лучшая известная реализация на данный момент.

Время работы tango-дерева [math]O(OPT_{dyn} \cdot \log \log n)[/math]

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

Рассмотрим для начала понятия online/offline динамически/статически оптимального дерева поиска.


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


Offline дерево поиска получает все запросы сразу и может использовать дополнительную память и вычисления для нахождения наиболее оптимальной последовательности обработки запросов. Стоимость работы дерева поиска для заданной последовательности ключей это стоимость доступа к каждому ключу и модификации дерева, и она не зависит от того, сколько времени мы потратили, чтобы найти оптимальную последовательность.

Online дерево поиска получает следующий запрос, только когда ответит на текущий, соответственно время работы пропорциональное стоимости исполнения запросов. Таким является splay-дерево.


Определение:
Пусть [math]OPT(S)[/math] — оптимальное время работы бинарного дерева поиска для последовательности запросов [math]S[/math]. Если стоимость запросов в бинарном дереве поиска — [math]O(n + OPT(S))[/math] для всей ключей от [math] 1 [/math] до [math] n [/math], то дерево называется динамически оптимальным.

Это свойство трудно показать. Неизвестно, есть ли какое-то динамически оптимальное online бинарное дерево поиска, и также неизвестно полиномиальное время для вычисления [math]OPT(S)[/math] с точностью до константы. Обозначим время работы динамически оптимального дерева [math]O(OPT_{dyn})[/math], где [math]OPT_{dyn} = n + OPT(S)[/math].

Гипотеза:
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] — ключ, к которому мы обращаемся.

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

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

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

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

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

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


1) Запрос вершины 3 : вершина 3; 2) Запрос 2 : вершина 3 – вершина 1 – вершина 2; 3) Запрос 4 : вершина 3 – вершина 4


Определение:
Фазовая диаграмма (диаграмма состояния) работы с деревом — графическое отображение состояния дерева, при котором координата точки [math](x_{i}, i)[/math] означает обращение к элементу [math]x_{i}[/math] в момент времени [math]i[/math].


Теорема:
Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.
Доказательство:
[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 \ne x[/math], то все хорошо, значит в дереве поиска она находится между [math]x[/math] и [math]y[/math], поэтому мы к нему обращались в то время, когда шли к [math]x[/math], значит есть точка на стороне нашего многоугольника.

t — наименьший общий предок х и у

Если [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 \ne 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(x) = \Omega(f) [/math]

Если что-то работает за [math]O(f \cdot g)[/math], значит это работает не более, чем в [math]g[/math] раз хуже.

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

Можно показать, что [math]OPT(x) \geqslant M + MP / 2[/math], где [math]M[/math] — число запросов, [math]MP[/math] — максимальное число независимых прямоугольников.

То есть [math]OPT(x) = \Omega(M + MP / 2)[/math]

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

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

Рассмотрим запросы [math]x_{i}, i = 0..j[/math]

Пусть [math]a \lt x_{j} \lt b[/math], где [math]a[/math] и [math]b[/math] — левая и правая границы на момент [math]i[/math]. На момент времени [math] i = 0 : a = -\infty, b = +\infty[/math]. Будем передвигать левую границу каждый раз, когда встречаем число [math]x_{i} : \{x_{j} \lt x_{i} \lt a\} [/math]. Аналогично правую. В каждый момент времени позиция [math]a[/math] может увеличиваться, [math]b[/math] уменьшаться. Рано или поздно, наши границы [math]a[/math] и [math]b[/math] встретятся в [math]x_{i} = x_{j}[/math]

Напишем [math]r[/math], если изменяется правая граница [math]b[/math] и [math]l[/math] — если левая.


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


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

[math]OPT \geqslant \sum\limits_{j \in [1, n]} 1 + ch(j)[/math]

Это можно вывести из предыдущей оценки, построив соответствующее [math]ch(j)[/math] множество попарно независимых прямоугольников.

DariaPicture12.png


Определение:
Жирное ребро (англ. Prefered edge) — ребро, соединяющее вершину с ее последним посещенным ребенком.


Теорема:
Рассмотрим [math]n[/math] ключей и [math]m[/math] запросов [math]x_{1} .. x_{m}[/math]

Организуем их в полное двоичное сбалансированное дерево. Если [math]n[/math] — не степень двойки, то на последний уровень будет заполнен не до конца.

Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.

Для каждой вершины будем запоминать жирное ребро.

Утверждается, что [math]\sum\limits_{i \in [1, n]} ch(i) \geqslant \sum\limits_{i \in [1, n]} K[/math], где [math]K[/math] — число изменений жирных ребер.

То есть если мы улучшили правую границу (мы искали что-то справа), а потом улучшили левую (искали слева от нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.

Tango-деревья

Построение

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


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


DariaPicture7.png

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

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

Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.


DariaPicture8.png

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

Каждый жирный путь — splay-дерево, и каждая вершина дерева указывает на корень другого splay-дерева, в котором лежит сын вершины по нежирному ребру.

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

Общее время работы дерева [math](M + K) \cdot \log \log n[/math], где [math]K[/math] — число изменений жирных ребер, [math]M[/math] — число запросов.

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

Поиск

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

Начинаем с поиска в жирном пути корня tango-дерева — splay-дереве.

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

Поиск в splay-дереве (синее дерево в splay-дереве) работает за высоту от количества вершин (количество вершин — длина жирного пути ([math]\log n[/math])) — то есть за [math]\log \log n[/math].

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

Пример

Изменение жирных ребер в бинарном дереве поиска

DariaPicture4.png DariaPicture5.png DariaPicture6.png

Соответствие tango-дерева текущему бинарному дереву поиска

DariaPicture14.png DariaPicture13.png DariaPicture8.png

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

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

Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: [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 \cdot split + 3 \cdot merge) \cdot K = (O(1) + 3 \cdot O(\log \log n) + 3 \cdot O(\log \log n)) \cdot K[/math] = [math]O(\log \log n \cdot OPT_{dyn}) [/math], где [math]K[/math] — число изменений жирного ребра, [math]n[/math] — число вершин в tango-дереве.


Пример

DariaPicture9.png


Операции вставки и удаления в tango-дереве не поддерживаются.

Источники информации