234
правки
Изменения
Нет описания правки
* '''link(u, w)''' {{---}} подвешивать одно дерево на другое;
* '''cut(v)''' {{---}} отрезать дерево с корнем в вершине v.
Среднее время выполнения каждой операции - <tex>O(\log(n))</tex>. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
==Решение задачи в частном случае==
{{Лемма
|id = Lemma1
|statement= На пути от вершины до корня не больше <tex>\log(n)</tex> легких ребер.
|proof = Пусть <tex>m</tex> {{---}} количество вершин в дереве с корнем в вершине, в которой мы сейчас находимся. Поднимаясь по легкому ребру, <tex>m</tex> увеличивается в два раза, поэтому, пройдя больше <tex>\log (n)</tex> легких ребер, получим <tex>m > n</tex>. Значит, в дереве не больше <tex>\log (n)</tex> легких ребер.
}}
Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>\mathrm{expose}</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2\log n</tex>
Докажем, что амортизационная стоимость операции <tex>\mathrm{expose}</tex> равна <tex>O(\log(n))</tex>
Пусть <tex>s(v)</tex> {{---}} количество вершин в поддеревьях <tex>v</tex> ( здесь имеется в виду splay-дерево пути, котоый строится в ходе выполнения <tex>\mathrm{expose}</tex>), <tex>r(v) = \log(s(v))</tex>. По [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>\mathrm{splay}</tex> не превосходит <tex>1 + 3 \cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>\mathrm{expose}</tex> ограничена следующим значением:
<tex>3 \cdot \log n - 3 \cdot \log (s(v)) + M</tex>
