амортизированная стоимость растянутого дерева: cost + P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x)) объяснение

Читая о растянутых деревьях, я нашел некоторое выражение о ранге растянутого узла «X» и амортизированной стоимости в википедии. Это дается как, { Мы можем ограничить амортизированную стоимость любой зигзагообразной или зигзагообразной операции следующим образом:

amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)),

где x - узел, перемещаемый к корню, а индексы «f» и «i» указывают после и до операции, соответственно. . При суммировании за всю операцию развертывания получается 3 (ранг (корень)), что составляет O (log n). Поскольку существует не более одной операции зигзага, это добавляет только константу.}

Я не могу это интерпретировать. Кто-нибудь может подробно объяснить вышесказанное. Если возможно, приведите несколько примеров.

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

Спасибо