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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 55: Строка 55:
  
 
|proof=
 
|proof=
#Фазовая диаграмма работы с деревом поиска обладает свойством древестности.
+
1. Фазовая диаграмма работы с деревом поиска обладает свойством древестности.
 
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.  
 
Пусть мы обращались к какому-то ключу <tex>x</tex> в <tex>i</tex>-ом запросе и к какому-то ключу <tex>y</tex> в <tex>j</tex>-ом запросе.  
 
Рассмотрим этот прямоугольник.
 
Рассмотрим этот прямоугольник.
Строка 68: Строка 68:
 
Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</tex>-го запроса,
 
Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</tex>-го запроса,
 
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
 
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
 +
 
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
 
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
 +
 
Если <tex>t != y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
 
Если <tex>t != y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.
 +
 
Если <tex>t = y</tex>, то есть <tex>y</tex> - предок <tex>x</tex> в момент <tex>j</tex>-го запроса,
 
Если <tex>t = y</tex>, то есть <tex>y</tex> - предок <tex>x</tex> в момент <tex>j</tex>-го запроса,
 
Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.
 
Значит <tex>y</tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю.
То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника
+
 
 +
То есть во время <tex>i</tex>-го запроса <tex>y</tex> был в поддереве <tex>x</tex>, а во время <tex>j</tex>-го запроса <tex>x</tex> в поддереве <tex>y</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>y</tex> к родителю, и мы обращались к <tex>y</tex>, следовательно есть точка на правой стороне нашего прямоугольника.
 +
 
 
  (рисунок надо?)
 
  (рисунок надо?)
  
# Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.
+
2. Если множество точек обладает свойством древесности, то оно является фазовой диаграммой работы с некоторым деревом поиска.
  
 
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
 
Для любого прямоугольника, построенного на наших точках, есть еще одна точка на стороне.
 +
 
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.  
 
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.  
  
Строка 91: Строка 97:
  
 
Рассмотрим общий случай
 
Рассмотрим общий случай
 +
 
Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.
 
Есть очередная горизонталь, на которой есть точки. Они по построению в текущий момент имеют минимальный приоритет, поэтому как-то организованы в районе корня нашего декартового дерева.
 +
 
Обойдем эти точки.
 
Обойдем эти точки.
 +
 
После этого мы должны перестроить наше дерево, изменив приоритеты.
 
После этого мы должны перестроить наше дерево, изменив приоритеты.
Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами
+
 
 +
Утверждается, что выполняя повороты только внутри верхней части нашего дерево можно построить дерево в соответствии с новыми приоритетами.
 +
 
 
Почему?
 
Почему?
 
Предположим, что это не удалось сделать.  
 
Предположим, что это не удалось сделать.  
 +
 
У нас есть вершина <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>y</tex>, чего мы делать не хотели в этой строке.
 +
 
Но тогда рассмотрим прямоугольник(мы обращались к <tex>x</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>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.
 
Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>x</tex>, но меньше <tex>y</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>y</tex>.
Строка 109: Строка 124:
  
 
Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.  
 
Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>y</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.  
 +
 
Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.
 
Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.
 +
 
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
 
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
 
}}
 
}}
Строка 121: Строка 138:
  
 
Рассмотрим запросы.
 
Рассмотрим запросы.
 +
 
Покроем их независимыми прямоугольниками.
 
Покроем их независимыми прямоугольниками.
 +
 
Прямоугольники независимы, если угол одного не лежит внутри другого.
 
Прямоугольники независимы, если угол одного не лежит внутри другого.
 +
 
Можно показать, что <tex>OPT >= M</tex>(число запросов) +  максимальное число независимых прямоугольников * 1/2
 
Можно показать, что <tex>OPT >= M</tex>(число запросов) +  максимальное число независимых прямоугольников * 1/2
 
==Вторая нижняя оценка Уилберра (Wilber) ==
 
==Вторая нижняя оценка Уилберра (Wilber) ==
 +
 
Рассмотрим запрос <tex>x</tex>
 
Рассмотрим запрос <tex>x</tex>
 +
 
Пусть левая граница <tex>= -inf</tex>, правая граница <tex>= +inf</tex>
 
Пусть левая граница <tex>= -inf</tex>, правая граница <tex>= +inf</tex>
 +
 
Идем от ключа <tex>x</tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
 
Идем от ключа <tex>x</tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
 +
 
И каждый раз, когда встречается значение большее, чем наше, но меньшее правой границы, мы сдвигаем правую границу.
 
И каждый раз, когда встречается значение большее, чем наше, но меньшее правой границы, мы сдвигаем правую границу.
 +
 
Аналогично с левой границей.
 
Аналогично с левой границей.
 +
 
Когда-то рано или поздно наши границы встретятся в <tex>x</tex>
 
Когда-то рано или поздно наши границы встретятся в <tex>x</tex>
 +
 
Можно показать, что из этой оценки выходит следующая оценка
 
Можно показать, что из этой оценки выходит следующая оценка
 +
 
Напишем <tex>r</tex>, если меняется правая граница и <tex>l</tex>  - если левая.
 
Напишем <tex>r</tex>, если меняется правая граница и <tex>l</tex>  - если левая.
 +
 
Назовем <tex>ch(i)</tex> количество смен <tex>r</tex> на <tex>l</tex> и обратно
 
Назовем <tex>ch(i)</tex> количество смен <tex>r</tex> на <tex>l</tex> и обратно
  
 
  <tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
 
  <tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
  
{{Теорема
+
{{Следствие
!!следствие
 
 
|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>
 
|statement=Рассмотрим <tex>n</tex> ключей и <tex>m</tex> запросов запросы <tex>x_{1} .. x_{m}</tex>
 +
 
Организуем их в полное двоичное сбалансированное дерево.
 
Организуем их в полное двоичное сбалансированное дерево.
  
 
Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!там
 
Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!там
 +
 
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
 
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
  
 
Утверждается, что  <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >=  <tex>\sum\limits_{i \in [1, n]}</tex> изменения числа жирных ребер.
 
Утверждается, что  <tex>\sum\limits_{i \in [1, n]} ch(i)</tex> >=  <tex>\sum\limits_{i \in [1, n]}</tex> изменения числа жирных ребер.
 +
 
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
 
То есть если мы улучшили правую границу(мы искали что-то справа), а потом улучшили левую(искали слева), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
 
}}
 
}}
Строка 161: Строка 192:
 
===Построение===
 
===Построение===
 
Пусть изначально все левые ребра были жирными.
 
Пусть изначально все левые ребра были жирными.
 +
 
Операций первого становления ребра жирным <tex>O(n)</tex> – дают несущественный вклад в асимптотику.  
 
Операций первого становления ребра жирным <tex>O(n)</tex> – дают несущественный вклад в асимптотику.  
  
 
Глубина нашего дерева <tex>log n</tex>.
 
Глубина нашего дерева <tex>log n</tex>.
 +
 
Из каждой вершины выходит <= 2 ребер.
 
Из каждой вершины выходит <= 2 ребер.
 +
 
В общем случае одно жирное, другое нет.
 
В общем случае одно жирное, другое нет.
 +
 
Все наше дерево можно разбить на жирные пути .
 
Все наше дерево можно разбить на жирные пути .
 +
 
[[Файл:DariaPicture7.png|400px|
 
[[Файл:DariaPicture7.png|400px|
 
]]
 
]]
  
 
Каждый из этих жирных путей организуем в свое splay-дерево.
 
Каждый из этих жирных путей организуем в свое splay-дерево.
 +
 
Из каждой вершины будет выходить вспомогательная ссылка на корень splay-дерева, соответствующего жирному пути в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.
 
Из каждой вершины будет выходить вспомогательная ссылка на корень splay-дерева, соответствующего жирному пути в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.
  
Строка 177: Строка 214:
  
 
Таким образом, все наши ключи организуют иерархичную структуру.
 
Таким образом, все наши ключи организуют иерархичную структуру.
 +
 
Каждый жирный путь  -- splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)
 
Каждый жирный путь  -- splay-дерево, и каждое их них указывает на корень дерева, в котором лежит ее второй сын(при этом указатель ставится на само дерево, а не на сына)
  
Строка 183: Строка 221:
 
===Поиск===
 
===Поиск===
 
Поиск ключа <tex>x</tex>.
 
Поиск ключа <tex>x</tex>.
 +
 
Ищем в корне tango-дерева – splay-дереве.
 
Ищем в корне tango-дерева – splay-дереве.
 +
 
Если не нашли, значит надо идти по нежирному ребру.
 
Если не нашли, значит надо идти по нежирному ребру.
 +
 
Пойдем по нему(красная стрелка) и ищем в новом дереве.
 
Пойдем по нему(красная стрелка) и ищем в новом дереве.
 +
 
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = <tex>log n</tex>) = <tex>log log n</tex>.
 
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина жирного пути = <tex>log n</tex>) = <tex>log log n</tex>.
  
Строка 193: Строка 235:
  
 
Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам.  
 
Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам.  
 +
 
//Теперь мы изменяем жирное ребро,  т е хотим отрезать 13 и подвесить 10 9
 
//Теперь мы изменяем жирное ребро,  т е хотим отрезать 13 и подвесить 10 9
 
//Отрезать 13 легко,  
 
//Отрезать 13 легко,  
Строка 200: Строка 243:
 
<tex>T1<T2</tex> сливаем в <tex>T, T1</tex> – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем <tex>Т2</tex>.
 
<tex>T1<T2</tex> сливаем в <tex>T, T1</tex> – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем <tex>Т2</tex>.
  
Но у нас <tex>Т1</tex> не меньше<tex> Т2</tex>
+
Но у нас <tex>T1</tex> не меньше<tex> T2</tex>
 +
 
 
Посмотрим на общий случай.
 
Посмотрим на общий случай.
 +
 
Был жирный путь.
 
Был жирный путь.
 +
 
Мы в нем что-то искали, не нашли, остановились в вершине, и хотим другое ее поддерево подклеить в жирный путь.
 
Мы в нем что-то искали, не нашли, остановились в вершине, и хотим другое ее поддерево подклеить в жирный путь.
 +
 
Заметим, что ее жирный путь с одной стороны в левом поддереве нашей вершины.
 
Заметим, что ее жирный путь с одной стороны в левом поддереве нашей вершины.
 +
 
С другой стороны в правом поддереве какого-то предка.
 
С другой стороны в правом поддереве какого-то предка.
 +
 
Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали.
 
Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали.
 +
 
И вставим наше поддерево в жирный путь.
 
И вставим наше поддерево в жирный путь.
 +
 
Теперь надо отрезать старое жирное ребро.
 
Теперь надо отрезать старое жирное ребро.
 +
 
Закончили в какой-то вершине, лежащей в жирном пути.
 
Закончили в какой-то вершине, лежащей в жирном пути.
 +
 
Надо посмотреть, в какую сторону вело жирное ребро.
 
Надо посмотреть, в какую сторону вело жирное ребро.
 +
 
Оно вело туда, куда мы не шли.
 
Оно вело туда, куда мы не шли.
 +
 
Мы знаем, что нужно вырезать из нашего дерева вершины, которые больше той, в которой мы закончили, но меньше того ключа, из которого мы последний раз шли не в ту сторону, в которую мы сейчас идем не по жирному ребру.
 
Мы знаем, что нужно вырезать из нашего дерева вершины, которые больше той, в которой мы закончили, но меньше того ключа, из которого мы последний раз шли не в ту сторону, в которую мы сейчас идем не по жирному ребру.
 +
 
Нас интересует ключ, который больше нашего, но который выше нас.
 
Нас интересует ключ, который больше нашего, но который выше нас.
Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей?.
+
 
 +
Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей?
 +
 
 
Но это дерево примитивное, оно является полным двоичным.
 
Но это дерево примитивное, оно является полным двоичным.
 +
 
В нем можем предподсчитать для каждой вершины минимум и максимум.
 
В нем можем предподсчитать для каждой вершины минимум и максимум.
 +
 
Значит, мы знаем интервал значений вершин его правого поддерева.
 
Значит, мы знаем интервал значений вершин его правого поддерева.
 +
 
И режем по минимальному и максимальному значениям в этом поддереве.
 
И режем по минимальному и максимальному значениям в этом поддереве.
  
Строка 223: Строка 284:
  
 
Разрезаем жирные ребра, по которым мы не прошли.
 
Разрезаем жирные ребра, по которым мы не прошли.
 +
 
Берем ребро. Берем дерево. Берем вершину. Split. Она корень.  
 
Берем ребро. Берем дерево. Берем вершину. Split. Она корень.  
 +
 
Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,
 
Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну,
вырезаем этот диапазон с помощью двух сплитов по rmin и по rmax.
+
вырезаем этот диапазон с помощью двух сплитов по <tex>r_{min}</tex> и по <tex>r_{max}</tex>.
 
В новое независимое дерево ставим красный указатель на вершину.
 
В новое независимое дерево ставим красный указатель на вершину.
 +
 
Старый красный указатель вел в дерево, которое надо слить с его предком.
 
Старый красный указатель вел в дерево, которое надо слить с его предком.
 +
 
Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли.
 
Разрезаем с другой стороны от нашей вершины и вставляем как сына по нежирному ребру к той вершине, от которой пошли.
  
 
Перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра
 
Перестройка = <tex>3 * split + 3 * merge</tex>, каждый из них за <tex>log log n = (O(1) + 3*O(log log n) + 3*O(log log n))</tex> * число изменений жирного ребра

Версия 01:36, 2 июня 2014

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


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

Определение:
Динамическая оптимальность (Dynamic Opt)


Если мы разрешаем перестраивать деревья в процессе запроса, то 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. делает какие-то количество поворотов

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

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

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

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

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

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


1) Запрос вершины 3 : вершина 3 2) Запрос 2 : вершина 3 – вершина 1 – вершина 2 3) Запрос 4 : вершина 3 – вершина 4
Утверждение:
Множество точек удовлетворяет свойству древесности, если на любом прямоугольнике с вершинами в наших точках есть еще хотя бы одна точка, отличная от точек, на которых его построили.
Теорема:
Множество точек является фазовой диаграммой работы с некоторым деревом поиска тогда и только тогда, когда оно обладает свойством древесности.
Доказательство:
[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], значит есть точка на стороне нашего многоугольника.

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 != 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]= -inf[/math], правая граница [math]= +inf[/math]

Идем от ключа [math]x[/math] назад и ищем, когда в предыдущий раз мы обращались к этому ключу.

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

Аналогично с левой границей.

Когда-то рано или поздно наши границы встретятся в [math]x[/math]

Можно показать, что из этой оценки выходит следующая оценка

Напишем [math]r[/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]
{{Следствие
|id=идентификатор (необязательно), пример: proposal1. 
|author=Автор утверждения (необязательно)
|about=О чем утверждение (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}

Tango-деревья

Пример

DariaPicture4.png DariaPicture5.png DariaPicture6.png

Построение

Пусть изначально все левые ребра были жирными.

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

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

Из каждой вершины выходит <= 2 ребер.

В общем случае одно жирное, другое нет.

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

DariaPicture7.png

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

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

DariaPicture8.png

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

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

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

Поиск

Поиск ключа [math]x[/math].

Ищем в корне tango-дерева – splay-дереве.

Если не нашли, значит надо идти по нежирному ребру.

Пойдем по нему(красная стрелка) и ищем в новом дереве.

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

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

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

Перестраивать дерево так, чтобы оно соответствовало новым жирным ребрам.

//Теперь мы изменяем жирное ребро, т е хотим отрезать 13 и подвесить 10 9 //Отрезать 13 легко, //- split по ключу, теперь х в корне, и отрезаем правое дерево. // Как обратно вставить 9 10 Merge в splay-дереве. [math]T1\lt T2[/math] сливаем в [math]T, T1[/math] – split от самой большой(самой правой) вершины, она становится конем, и в правое поддерево приклеиваем [math]Т2[/math].

Но у нас [math]T1[/math] не меньше[math] T2[/math]

Посмотрим на общий случай.

Был жирный путь.

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

Заметим, что ее жирный путь с одной стороны в левом поддереве нашей вершины.

С другой стороны в правом поддереве какого-то предка.

Соответственно, мы может наше splay-дерево разрезать на два по ключу, по которому мы искали.

И вставим наше поддерево в жирный путь.

Теперь надо отрезать старое жирное ребро.

Закончили в какой-то вершине, лежащей в жирном пути.

Надо посмотреть, в какую сторону вело жирное ребро.

Оно вело туда, куда мы не шли.

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

Нас интересует ключ, который больше нашего, но который выше нас.

Мы хотим отрезать все ключи, которые лежат в поддереве вершины в дереве жирных путей?

Но это дерево примитивное, оно является полным двоичным.

В нем можем предподсчитать для каждой вершины минимум и максимум.

Значит, мы знаем интервал значений вершин его правого поддерева.

И режем по минимальному и максимальному значениям в этом поддереве.

Итого

Разрезаем жирные ребра, по которым мы не прошли.

Берем ребро. Берем дерево. Берем вершину. Split. Она корень.

Смотрим интервал в базовом дереве – какой диапазон ключей соответствует нашему сыну, вырезаем этот диапазон с помощью двух сплитов по [math]r_{min}[/math] и по [math]r_{max}[/math]. В новое независимое дерево ставим красный указатель на вершину.

Старый красный указатель вел в дерево, которое надо слить с его предком.

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

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