Изменения

Пусть <tex>s(v)</tex> - количество вершин в поддеревьях <tex>v</tex> (здесь имеется в виду splay-дерево пути, котоый строится в ходе выполнения <tex>expose</tex>), <tex>r(v) = log(s(v))</tex>. По [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>splay</tex> не превосходит <tex>1 + 3 \times (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>expose</tex> ограничена следующим значением:

Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>expose</tex> равна <tex>O(\log n)</tex>