4551
правка
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Перейти к навигации
Перейти к поиску
м
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 00:12, 2 марта 2016
, 2 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Количество поворотов, необходимых для | Количество поворотов, необходимых для преобразования любого бинарного дерева с 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, то исходное дерево может повлиять только на константный множитель. | ||
== Основные результаты == | == Основные результаты == | ||