4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 18:54, 1 марта 2016
, 1 марта 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 28: | Строка 28: | ||
== Применение == | == Применение == | ||
Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность операций доступа занимает | Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность операций доступа занимает <math>\Theta (m \; log \; n)</math> времени. | ||
Но хотя улучшить асимптотический результат для случайной последовательности операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как косое дерево. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным. | Но хотя улучшить асимптотический результат для случайной последовательности операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным. | ||
| Строка 38: | Строка 38: | ||
В 2004 году Демейн и коллеги взялись за разработку альтернативных алгоритмов построения бинарного дерева поиска с небольшими, но неконстантными коэффициентами конкурентности [6]. Они предложили Tango – первую структуру данных, для которой доказано наличие нетривиального коэффициента конкурентности в виде O(log log n). Это большой шаг в направлении разработки O(1)-конкурентного алгоритма; данное направление исследований потенциально способно заменить значительное количество специализированных алгоритмов поддержки бинарных деревьев поиска. | В 2004 году Демейн и коллеги взялись за разработку альтернативных алгоритмов построения бинарного дерева поиска с небольшими, но неконстантными коэффициентами конкурентности [6]. Они предложили Tango – первую структуру данных, для которой доказано наличие нетривиального коэффициента конкурентности в виде O(log log n). Это большой шаг в направлении разработки O(1)-конкурентного алгоритма; данное направление исследований потенциально способно заменить значительное количество специализированных алгоритмов поддержки бинарных деревьев поиска. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
