234
правки
Изменения
Нет описания правки
= M + |H \cap S \rightarrow D| - |H \cap D \rightarrow S| \\
\leqslant M + |L \cap D \rightarrow S| - |H \cap D \rightarrow S| \\
= 2 \times cdot |L \cap D \rightarrow S| \\=2 \times cdot \log n
</tex>
}}
Докажем, что амортизационная стоимость операции <tex>expose</tex> равна <tex>O(log(n))</tex>
Пусть <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 cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>expose</tex> ограничена следующим значением:
<tex>3 \times cdot \log n - 3 \times cdot \log (s(v)) + M</tex>
Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>expose</tex> равна <tex>O(\log n)</tex>
