Изменения

Перейти к: навигация, поиск

Сверхбыстрый цифровой бор

1 байт убрано, 00:17, 9 июня 2013
Сверхбыстрый цифровой бор (y-fast-trie)
===find===
Находим succ = x среди представителей в x-fast-trie, а потом запускаем поиск succ(x) в дереве, подвешенном к листу x, а также в дереве, подвешенном к листу pred(x) среди представителей в x-fast-trie. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своим сакцессором и прецессором.
O(log w) на поиск в x-fast-trie и O(log w) на поиск в деревьях поиска, поэтому итогая асимптотика - O(log w).
succ & pred выполняются аналогично.
Анонимный участник

Навигация