Splay Tree的时间复杂度证明

文本统计：约 1238 个字

转载伸展树（Splay）复杂度证明 - Mr_Spade - 博客园 (cnblogs.com)

在文中我们用\(T\)表示一棵完整的\(Splay\ Tree\)，并（不严谨地）用\(|T|\)表示\(T\)这棵\(Splay\ Tree\)的节点数目。

如无特殊说明，小写英文字母（如\(x，y，z\)）在本文中表示\(T\)的一个节点，并（不严谨地）用\(|x|\)表示以节点\(x\)为根的子树的大小，\(x∈T\)表示节点\(x\)在\(T\)中。

一般我们默认\(x′\)代表节点\(x\)在经过了上下文中描述的操作以后的状态，因此对应的\(x\)代表之前的状态。

我们用\(Φ(T)\)表示整棵\(Splay Tree\)的势能函数，\(ϕ(x)\)则表示节点\(x\)对\(T\)贡献的势能。

先来讲一下我们的势能函数，我们定义：

\[ ϕ(x)=log|x| \]
\[ Φ(T)=∑_{x∈T}ϕ(x) \]

可以发现，对于任意时刻，因为\(|x|≥1\)，因此\(log⁡|x|≥0\)，从而得到\(Φ(T)≥0\)，因此势能函数是合法的。同时\(∀|x|≤|T|\)，因此我们总有\(Φ(T)≤|T|log⁡|T|\)。这个上界是比较松的，但是对我们的分析没有影响。

下面考虑一次伸展操作对于势能函数的影响。由于我们可以把从根向下查找的代价计算到伸展过程中对应的旋转操作上，此时旋转操作复杂度不变，只是常数增大，从而忽略了查找对复杂度的影响。我们可以简单地通过增大势的单位来支配隐藏在操作中的常数。因此我们只需证明对于一次伸展操作的所有旋转操作，其复杂度是均摊\(O(log⁡|T|)\)的，我们就完成了对\(Splay\ Tree\)复杂度的证明。

  1. \(zig\)操作

由于\(zag\)操作与\(zig\)相似，因此只需要证明\(zig\)即可。

假设我们\(zig\)的对象是\(x\)，其父亲为\(y\)，显然在旋转以后，只有\(x\)和\(y\)的子树大小发生了变化。因此势能变化量为：

\[ ΔΦ(T)=ϕ(x′)+ϕ(y′)−ϕ(x)−ϕ(y) \]

显然\(ϕ(x′)=ϕ(y)\)，且\(ϕ(x′)≥ϕ(y′)\)，因此消去\(ϕ(x′)\)与\(ϕ(y)\)，并将\(ϕ(y′)\)替换为\(ϕ(x′)\)，有：

\[ ΔΦ(T)≤ϕ(x′)−ϕ(x) \]

因此\(zig\)操作的均摊代价为\(O(1+ϕ(x′)−ϕ(x))\)，其中\(O(1)\)代表旋转操作本身的复杂度，而在一次伸展操作中也只会有一次\(zig\)操作，因此这额外的\(O(1)\)代价不会对分析造成影响，因此我们可以只关心其中的\(O(ϕ(x′)−ϕ(x))\)。

  1. \(zig−zig\)操作

由于\(zag−zag\)操作与\(zig−zig\)相似，因此只需要证明\(zig−zig\)即可。

假设我们\(zig−zig\)的对象是\(x\)，其父亲为\(y\)，其祖父为\(z\)，与\(zig\)操作类似，势能变化量为：

\[ ΔΦ(T)=ϕ(x′)+ϕ(y′)+ϕ(z′)−ϕ(x)−ϕ(y)−ϕ(z) \]

同样地，由于\(ϕ(x′)=ϕ(z)\)，因此将它们消去：

\[ ΔΦ(T)=ϕ(y′)+ϕ(z′)−ϕ(x)−ϕ(y) \]

而我们又有\(ϕ(x′)≥ϕ(y′)，ϕ(x)≤ϕ(y)\)，因此有：

\[ ΔΦ(T)≤ϕ(x′)+ϕ(z′)−2ϕ(x) \]

推到这里，我们先来做一个小工作，来证明\(ϕ(x)+ϕ(z′)−2ϕ(x′)\)（注意与上面的式子不一样）的值不大于\(−1\)。

假设\(|x|=a\)，\(|z′|=b\)，那么我们有：

\[ ϕ(x)+ϕ(z′)−2ϕ(x′)=log⁡|x|+log⁡|z′|−2log⁡|x′| \]

我们将\(log\)合并，得到：

\[ ϕ(x)+ϕ(z′)−2ϕ(x′)=log⁡(\frac{|x||z′|}{|x′|^2}) \]

由于\(|x′|≥a+b\)（可以结合旋转过程思考一下），而\(log\)是单调的，因此：

\[ ϕ(x)+ϕ(z′)−2ϕ(x′)≤log⁡(\frac{ab}{(a+b)^2})≤log⁡(\frac{ab}{2ab})≤−1 \]

证明完毕。现在我们已经知道\(zig−zig\)操作的摊还代价不大于：

\[ O(1)+ϕ(x′)+ϕ(z′)−2ϕ(x) \]

其中\(O(1)\)为旋转操作的复杂度。由于之前的推导我们可以知道\(ϕ(x)+ϕ(z′)−2ϕ(x′)≤−1\)，因此\(−1−(ϕ(x)+ϕ(z′)−2ϕ(x′))≥0\)，我们在摊还代价上加上这个非负数得到：

\[ O(1)+ϕ(x′)+ϕ(z′)−2ϕ(x)−1−(ϕ(x)+ϕ(z′)−2ϕ(x′)) \]

化简一下，就得到：

\[ O(1)+O(ϕ(x′)−ϕ(x))−1 \]

通过增大我们刚刚加的那个非负数以及势的单位，我们就可以支配隐藏在 \(O(1)\) 中的常数，因此一次\(zig−zig\)操作的摊还代价为：

\[ O(ϕ(x′)−ϕ(x)) \]
  1. \(zig−zag\)操作

分析的过程和\(zig−zig\)操作完全一样，之前分析用到的所有性质此时仍然适用，因此略过分析过程。其摊还代价依然为：

\[ O(ϕ(x′)−ϕ(x)) \]
  1. 总结

综上所述，除了最后一次旋转可能增加\(O(1)\)的代价以外，其余操作的摊还代价只和我们伸展的对象xx的势有关。我们假设旋转操作一共执行了\(n\)次，并用\(x_i\)来表示节点\(x\)在经过\(i\)次旋转后的状态，那么整一个伸展操作的摊还代价就为：

\[ O(1+∑_{i=1}^nϕ(xi)−ϕ(xi−1)) \]

显然除了\(ϕ(x_n)\)与\(ϕ(x_0)\)外，所有的势都被抵消了，因此摊还代价为：

\[ O(1+ϕ(x_n)−ϕ(x_0)) \]

至此，我们不必关心\(ϕ(x_0)\)的值了。此时\(x_n\)是整棵\(Splay\ Tree\)的根，因此\(ϕ(x_n)=log|T|\)。我们成功的证明了一次伸展操作的摊还代价为\(O(log|T|)\)。

\(\Leftarrow\) 返回Lecture1

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！