94
правки
Изменения
Нет описания правки
Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>2(r'(x) - r(x)) \le 3(r'(x) - r(x))</tex>.
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(x) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay <tex>T_{splay} \le O(\log_2 N) - O(\log_2 СC(x)) + O(1) = O(\log_2 N)</tex>, где <tex>N</tex> - число элемнтов в дереве.
}}
