4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Материал из WEGA
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 18:49, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
В силу этого количество поворотов, необходимых для изменения любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что OPT(S; | В силу этого количество поворотов, необходимых для изменения любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что <math>OPT(S, T_0) \;</math> отличается от <math>OPT(S, T_0') \;</math> не более чем на 2n - 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель. | ||
== Основные результаты == | == Основные результаты == | ||
