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

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