Изменения
→Анализ операции splay
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>v</tex> — это величина, обозначаемая <tex>r(v)</tex> и равная <tex>\log_2 C(v)</tex>, где <tex>C(v)</tex> — количество вершин в поддереве с корнем в <tex>v</tex>.
{{Лемма
|statement=
Амортизированное время операции splay вершины <tex>v</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(v) + 1</tex>
|proof=
Проанализируем каждый шаг операции splay. Пусть <tex>r'</tex> и <tex>r</tex> — ранги вершин после шага и до него соответственно, <tex>u</tex> — предок вершины <tex>v</tex>, а <tex>w</tex> — предок <tex>u</tex> (если есть).
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(v) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
}}
==Литература==
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"
