4446
правок
O(log log n)-конкурентное бинарное дерево поиска: различия между версиями
Перейти к навигации
Перейти к поиску
м
O(log log n)-конкурентное бинарное дерево поиска (посмотреть исходный код)
Версия от 00:11, 2 марта 2016
, 2 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ..., s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута | Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ..., s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута <math>s_i \;</math>. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов. | ||