4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 00:15, 2 марта 2016
, 2 марта 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 28: | Строка 28: | ||
== Применение == | == Применение == | ||
Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность операций доступа занимает <math>\Theta (m \; log \; n)</math> времени. | Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует лучшей теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность операций доступа занимает <math>\Theta (m \; log \; n)</math> времени. | ||
