Что такое амортизируемая сложность в Splay Tree?

Question

Я попытался понять амортизированную сложность и сделал несколько поисков в сети, но пока не смог найти хороший ресурс.

Так может ли кто-нибудь объяснить, что такое амортизируемая сложность и как она становится O(lg n) в Splay Tree на одну операцию?

Answer 1

Любая операция, выполняемая с деревьями сплайсинга, независимо от того, вставлена ​​ли операция удаления и т. Д., В стоимости преобладает операция сплайсинга. следовательно, учитывается стоимость только операции расширения, которая представляет собой повороты, выполняемые на узле, который должен быть развернут.

The amortized function is given by a=c+3Rfinal(v)-3Rinitial(v)

где a - амортизированная стоимость, c - фактическая стоимость, Rfinal - ранг после операции преобразования, а Rinitial - ранг узла перед вращением.(ранг любого узла определяется высотой его поддерева, т. е. log|S| где S - число узлов, укорененных под ним)

Теперь рассмотрим наихудший случай, когда узел, который должен быть развернут, является листом, поэтому его начальный ранг равен 0. После расширения его до вершины, то есть в качестве корневого узла его ранг становится log n, где n - общее количество узлов в дереве.,

 a<= 2+3logn-0
 O(logn).