96
правок
Изменения
м
→Поиск элемента
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.
Таким образом, сложность получается логарифмическая, '''НОНо!''' При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
