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

Данная модель алгоритма [[Binary search tree|бинарного дерева поиска]] (binary search tree, BST) используется в большинстве посвященных ему работ; она была детально изложена Уилбером [22]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей.