O(log log n)-конкурентное бинарное дерево поиска: различия между версиями

Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ..., s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута <math>s_i \;</math>. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов.

Количество поворотов, необходимых для преобразования любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что <math>OPT(S, T_0) \;</math> отличается от <math>OPT(S, T_0') \;</math> не более чем на 2n - 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель.

Границей чередования является нижняя граница <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>.

Время выполнения алгоритма Tango BST на последовательности S из m операций доступа составляет <math>O((OPT(S, T_0)) + n) * (1 + log \; log \; n))</math>.

Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует лучшей теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность из m операций доступа занимает <math>\Theta (m \; log \; n)</math> времени.

Но хотя улучшить асимптотический результат для случайной последовательности m операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным.

За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время выполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1].

Tango [6] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [22] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян) [14], Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер) [22], В поисках динамической оптимальности (Демейн и коллеги) [6] и Динамическое O(log log n)-конкурентное бинарное дерево поиска (Ван и коллеги) [21].