4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 18:46, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Данная модель алгоритма бинарного дерева поиска (binary search tree, BST) используется в большинстве посвященных ему работ; она была детально изложена Уилбером [ ]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей. | Данная модель алгоритма [[Binary search tree|бинарного дерева поиска]] (binary search tree, BST) используется в большинстве посвященных ему работ; она была детально изложена Уилбером [22]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей. | ||
| Строка 15: | Строка 15: | ||
В силу этого количество поворотов, необходимых для изменения любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что OPT(S; T0) отличается от OPT(S; T00) не более чем на 2и- 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель. | В силу этого количество поворотов, необходимых для изменения любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что OPT(S; T0) отличается от OPT(S; T00) не более чем на 2и- 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель. | ||
== Основные результаты == | == Основные результаты == | ||
