algorithm - 伸展树(Splay Tree)的摊销成本 : cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)) explanation

Question

在阅读有关 splay 树的文章时，我在维基百科中发现了一些关于 splay 节点“X”等级和摊销成本的表达方式。它被给出为，{我们可以通过以下方式限制任何 zig-zig 或 zig-zag 操作的摊销成本:

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

其中x是向根移动的节点，下标“f”和“i”分别表示操作前后。当对整个 splay 操作求和时，这会伸缩到 3(rank(root))，即 O(log n)。由于最多有一个 zig 操作，因此这只会添加一个常量。

我无法解释这个。请有人详细解释以上内容。如果可能的话，举一些例子。

请提供一些解释其他splay树定理的链接

谢谢

Answer 1

您想对静态伸展树(Splay Tree)进行简单的摊销分析。如果你像维基百科上的例子那样采用一个基本的之字形。这是最坏的情况。你有:

P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x))

证明:使用维基百科上使用的符号，因为转换后 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)

您可以将其推广到整个操作以计算摊销成本。

我猜它证明了你的结果，但我不确定这是否是你要找的。