24
правки
Изменения
м
Исправлена описка
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся содержаться все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{---}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
'''function''' cut(v: '''tree'''):
Докажем, что [[Амортизационный анализ|амортизационная стоимость операции]] <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>
