4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Перейти к навигации
Перейти к поиску
м
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 18:53, 1 марта 2016
, 1 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Основные результаты == | == Основные результаты == | ||
Границей чередования является нижняя граница OPT(S; | Границей чередования является нижняя граница <math>OPT(S, T_0) \;</math>, зависящая только от S. Рассмотрим любое бинарное дерево поиска P, состоящее из всех элементов <math>T_0 \;</math>. Для каждой вершины y в P определим левую сторону y, включающую все вершины левого поддерева y и саму y, а также правую сторону y, включающую все вершины правого поддерева y. Для каждой вершины y пометим каждую операцию доступа к <math>s_i \;</math> в S меткой, обозначающей, находится ли она на левой или правой стороне y, игнорируя все операции, производимые над другими поддеревьями, отличными от y. Обозначим количество изменений метки для y как IB(S; y). Граница чередования IB(S) составляет <math>\sum_y IB(S, y) \;</math>. | ||
Теорема 1 (Нижняя граница чередования [6, 22]) IB(S)/2 | '''Теорема 1 (Нижняя граница чередования [6, 22]). IB(S)/2 - n – ''нижняя граница'' <math>OPT(S, T_0) \;</math>.''' | ||
Демейн и коллеги заметили, что эту нижнюю границу невозможно использовать для улучшения конкурентного соотношения относительно | Демейн и коллеги заметили, что эту нижнюю границу невозможно использовать для улучшения конкурентного соотношения относительно <math>\Theta (log \; log \; n)</math>. | ||
Теорема 2. (Алгоритм Tango является O( | '''Теорема 2. (Алгоритм Tango является <math>O(log \; log \; n)</math>-конкурентным BST-алгоритмом [6]).''' | ||
Время исполнения алгоритма Tango BST на последовательности S из m операций доступа составляет <math>O((OPT(S, T_0)) + n) * (1 + log \; log \; n))</math>. | |||
== Применение == | == Применение == | ||