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

== Открытые вопросы ==

Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано.

Задача нахождения o(loglog n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени исполнения.

== См. также ==