展开树的摊销成本:成本+ P(tf) - P(ti)≤3(rankf(x) - ranki(x))解释

Question

在阅读splay树时,我发现了一些关于splay节点'X'的等级和维基百科中的摊销成本的表达式.它被赋予,{我们可以通过以下方式约束任何zig-zig或Zig-zag操作的摊销成本:

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

其中x是向根移动的节点,下标"f"和"i"分别表示在操作之后和之前.当对整个展开操作求和时,这个望远镜达到3(秩(根)),即O(log n).由于最多只有一个zig操作,这只会增加一个常量.}

我无法解释这一点.有人可以详细解释上面的内容.如果可能,举一些例子.

请提供一些链接,以解释其他定义树的定理

谢谢

Answer 1

您想要对静态展开树进行简单的摊销分析。\n如果您采用一个基本的之字形，如维基百科上的示例。这是最坏的情况。\n你有：

\n\n

P(tf) - P(ti) \xe2\x89\xa4 3(rankf(x) -ranki(x))

\n\n

证明：\n使用维基百科上使用的符号，由于 x 在变换后位于树的根处，因此您可以轻松得到：

\n\n

rankf(x)>=rankf(g) 且rankf(x)>=rankf(f)

\n\n

因此，

\n\n

Ptf = rankf(x)+rankf(g)+rankf(p) <= 3*rankf(x)

\n\n

在转换之前对 x 进行相反的推理，您会得到：

\n\n

Pti = 兰基(x)+兰基(g)+兰基(p) >= 3*兰基(x)

\n\n

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

\n\n

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

\n