4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Перейти к навигации
Перейти к поиску
м
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 00:14, 2 марта 2016
, 2 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Основные результаты == | == Основные результаты == | ||
Границей чередования является нижняя граница <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 | Границей чередования является нижняя граница <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>. | ||