在阅读有关展开树的信息时，我发现了一些关于展开节点“X”的等级和维基百科中的摊销成本的表达。它给出为 { 我们可以通过以下方式限制任何锯齿形或锯齿形操作的摊销成本：
amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)),
其中x是向根移动的节点，下标“f”和“i”分别表示操作之后和之前。当对整个展开操作求和时，它会伸缩到 3(rank(root))，即 O(log n)。由于最多有一个 zig 操作，这只会增加一个常数。}
我无法解释这一点。请有人详细解释上述内容。如果可能的话，举一些例子。
请提供一些链接以解释伸展树的其他定理
谢谢
您想对静态展开树进行简单的摊销分析。如果您像维基百科上的示例一样采用基本的之字形。这是最坏的情况。你有 ：
P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x))
证明：使用 wikipedia 上使用的符号，由于 x 在转换后位于树的根部，因此您很容易得到：
rankf(x)>= rankf(g) 和 rankf(x)>= rankf(f)
因此，
Ptf = rankf(x)+rankf(g)+rankf(p) <= 3*rankf(x)
在转换之前使用 x 的相反推理，您会得到：
Pti = ranki(x)+ranki(g)+ranki(p) >= 3*ranki(x)
您可以将其推广到整个操作以计算摊销成本。
我想它证明了你的结果，但我不确定这是你要找的。