伸展树的原理及应用.doc

伸展树的原理及应用
常州市第一中学 林厚从
【摘要】
本文介绍了伸展树的基本概念、基本操作及其应用，全文分为四个部分：
第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高的缺点，以及平衡树编程复杂度又过高的困惑，从而引入时间复杂度和编程复杂度都更为优秀的伸展树。
第二部分介绍了伸展树的基本操作，并给出了伸展树操作时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊时间复杂度均为O(log2n)，说明伸展树是一种较平衡的二叉查找树。
第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。
第四部分指出了伸展树的优点，总结全文，给出本文的一些附录。
【第一部分 引言】
二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉查找树有着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。
作用于二叉查找树上的基本操作的时间复杂度是与树的高度成正比的。对一棵n个结点的二叉树，这些操作在最优情况下运行时间为O(log2n)。但如果二叉树退化成n个结点的线性链，则这些操作在最坏情况下的运行时间为O(n)。有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，如平衡树（AVL）等。但是需要额外的空间来存储平衡信息，且实现起来比较复杂。同时，如果访问模式不均匀，平衡树的效率就会受到影响。而伸展树却可以克服这些问题。
伸展树（Splay Tree），是由Daniel Sleator和Robert Tarjan创造，也是对二叉查找树的一种改进。虽然它并不能保证树一直是“平衡”的，但对于它的一系列操作，可以证明其每一步操作的“平摊时间”复杂度都是O(log2n)，平摊时间是指在一系列最坏情况的操作序列中单次操作的平均时间。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求（不需要记录用于平衡的冗余信息）和编程复杂度也都是很优秀的。
获得较好平摊效率的一种方法就是使用“自调整”的数据结构。与平衡结构或有明确限制的数据结构相比，自调整的数据结构有以下几个优点：
1、从平摊角度来说，它们忽略常量因子，因此绝对不会差于有明确限制的数据结构。而且由于它们可以根据具体使用情况进行调整，所以在使用模式不均匀的情况下更加有效；
2、由于无需存储平衡信息或者其它限制信息，所以所需的存储空间更小；
3、它们的查找和更新算法概念和操作都很简单，易于实现。
当然，自调整结构也有其潜在的缺点：
1、它们需要更多的局部调整，尤其是在查找期间。而那些有明确限制的数据结构仅需要在更新期间进行调整，查找期间则不用；
2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是一个不足之处。

【第二部分 伸展树的基本操作】
伸展树是对二叉查找树的一种改进。与二叉查找树一样，伸展树也具有有序性，即伸展树中的每一个结点x都满足：该结点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。但是与普通二叉查找树不同的是，伸展树可以“自我调整”，这就要依靠伸展树的核心操作——伸展操作Splay(x,S)。
一、伸展操作Splay(x,S)
伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转，将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理：
情况一：结点x的父结点y是根结点。这时，如果x是y的左孩子，则我们进行一次Zig（右旋）操作；如果x是y的右孩子，则我们进行一次Zag（左旋）操作。经过旋转，使x成为二叉查找树S的根结点，调整结束。如图1所示：

图 1、ZIG或ZAG

图 2、ZIG-ZIG

情况二：结点x的父结点y不是根结点。则我们设y的父结点为z，且x与y同时是各自父结点的左孩子、或者同时是各自父结点的右孩子。这时，我们进行一次Zig-Zig操作、或者Zag-Zag操作。如图2所示：
情况三：结点x的父结点y不是根结点。则我们设y的父结点为z，且x与y中一个是其父结点的左孩子、而另一个是其父结点的右孩子。这时，我们进行一次Zig-Zag操作、或者Zag-Zig操作。如图3所示：

图 3、ZIG-ZAG

下面举一个例子来体会上面的伸展操作。如图4所示，最左边的一个单链先执行Splay(1,S)，我们将元素1调整到了伸展树S的根部。如图5所示，再执行Splay(2,S)，将元素2调整到了伸展树S的根部。从直观上可以看出在经过调整后，伸展树比原来“平衡”了许多。而伸展操作的过程并不复杂，只需要根据上述三种情况进行旋转就可以了，而三种旋转都是由基本的左旋和右旋组成的，实现较为简单。

图4、Splay(1,S)

图5、Splay(2,S)

二、伸展树的基本操作
利用Splay操作，我们可以在伸展树S上进行如下几种基本运算。

1、Find(x,S)：判断元素x是否在伸展树S表示的有序集中。
首先，与在二叉查找树中进行的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。

2、Insert(x,S)：将元素x插入到伸展树S表示的有序集中。
首先，与在二叉查找树中进行插入操作一样，将x插入到伸展树S中的相应位置，再执行Splay(x,S) 调整伸展树。

3、Join(S1,S2)：将两棵伸展树S1与S2合并成为一棵伸展树。其中S1的所有元素都小于S2的所有元素。
首先，找到伸展树S1中最大的一个元素x，再通过Splay(x,S1)将x调整到伸展树S1的根。然后再将S2作为x结点的右子树，这样就得到了新的伸展树S。如图6所示：

图6、Join(S1,S2)
4、Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。
先执行Find(x,S)将x调到根，然后再对左右子树执行Join(S1,S2)。

5、Split(x,S)：以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。
首先执行Find(x,S)，将元素x调整为伸展树的根结点，则x的左子树就是S1，而右子树就是S2。如图7所示：

图7、Split(x,S)
除了上面介绍的五种基本操作外，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。

三、伸展树的基本操作的算法实现
1、伸展树类型的定义
Type
Tpoint=^Trec;
Trec=Record
Key:integer; //关键字
Father,LeftChild,RightChild:Tpoint; //父结点、左孩子、右孩子
End;
Var
S:Tpoint; //变量S记录根结点

2、伸展操作
2.1、左旋操作:zag
Procedure LeftRotate(x:Tpoint);
Var y:Tpoint;
Begin
y:=x^.Father; //找到y

y^.RightChild:=x^.LeftChild; //把x的左孩子赋给y的右孩子
if x^.LeftChild<>nil //如果x确实有左孩子的话
then x^.LeftChild^.Father:=y; //则把x的左孩子的父结点接到y上

x^.Father:=y^.Father; //将x连到y的父结点上
if y^.Father<>nil then begin //如果y不是根结点
if y=y^.Father^.LeftChild //如果y是左孩子
then y^.Father^.LeftChild:=x //则把x置为y的父结点的左孩子
else y^.Father^.RightChild:=x;//否则把x置为y的父结点的右孩子
end;
y^.Father:=x; //把y的父结点置为x
x^.LeftChild:=y; //把x的右孩子置为y
End;

2.2、右旋操作:zig
Procedure RightRotate(x:Tpoint);
Var y:Tpoint;
Begin
y:=x^.Father; //找到y

y^.LeftChild:=x^.RightChild; //把x的右孩子赋给y的左孩子
if x^.RightChild<>nil //如果x确实有右孩子的话
then x^.RightChild^.Father:=y;//则把x的右孩子的父结点接到y上

x^.Father:=y^.Father; //将x连到y的父结点上
if y^.Father<>nil then begin //如果y不是根结点
if y=y^.Father^.LeftChild //如果y是左孩子
then y^.Father^.LeftChild:=x //则把x置为y的父结点的左孩子
else y^.Father^.RightChild:=x;//否则把x置为y的父结点的右孩子
end;
y^.Father:=x; //把y的父结点置为x
x^.RightChild:=y; //把x的右孩子置为y
End;

2.3、伸展操作
Procedure Splay(var x,S:Tpoint);
Var p:Tpoint;
Begin
while x^.Father<>nil do
begin
p:=x^.Father;

if p^.Father=nil then begin
if x=p^.LeftChild
then RightRotate(x) //Zig
else LeftRotate(x); //Zag
break;
end;

if x=p^.LeftChild then begin
if p=p^.Father^.LeftChild then begin //Zig-Zig
RightRotate(p);
RightRotate(x);
end
else begin //Zig-Zag
RightRotate(x);
LeftRotate(x);
end;
end
else begin
if p=p^.Father^.RightChild then begin //Zag-Zag
LeftRotate(p);
LeftRotate(x);
end
else begin //Zag-Zig
LeftRotate(x);
RightRotate(x);
end;
end;
end;

S:=x; //x为树的根结点
End;

3、查找
Function Find(x:integer; var S:Tpoint):Tpoint;
Var p:Tpoint;
Begin
p:=BST_Search(x,S); //与普通二叉查找树相同，找到该结点
Splay(p,S); //将该结点调整到S的根部
Find:=p;
End;

4、插入
Procedure Insert(x:integer; var S:Tpoint);
Begin
BST_Insert(x,S); //与普通二叉查找树相同，插入该元素
Splay(x,S); //将该结点调整到S的根部
End;

5、删除
Procedure Delete(x:integer; var S:Tpoint);
Var p:Tpoint;
Begin
p:=Find(x,S); //找到这个结点，x成为树根
S:=Join(p^.LeftChild,p^.RightChild); //合并操作见下文
End;

6、求最大值
Function Maximum(S:Tpoint):Tpoint;
Var p:Tpoint;
Begin
p:=S;
while p^.RightChild<>nil do p:=p^.RightChild; //树最右下端就是最大值
Splay(p,S); //将最大值调整为根
Maximum:=p;
End;

7、求最小值
Function Minimum(S:Tpoint):Tpoint;
Var p:Tpoint;
Begin
p:=S;
while p^.LeftChild<>nil do p:=p^.LeftChild; //树最左下端就是最小值
Splay(p,S); //将最小值调整为根
Minimum:=p;
End;

8、求前趋
Function Predecessor(x:integer; var S:Tpoint);
Var p:Tpoint;
Begin
p:=Find(x,S); //将x调整为根
p:=p^.LeftChild;
Predecessor:=Maximum(p); //前趋即为左子树的最大值
End;

9、求后继
Function Successor(x:integer; var S:Tpoint);
Var p:Tpoint;
Begin
p:=Find(x,S); //将x调整为根
p:=p^.RightChild;
Successor:=Minimum(p); //后继即为右子树的最小值
End;

10、合并
Function Join(S1,S2:Tpoint):Tpoint;
Var p:Tpoint;
Begin
if S1=nil then begin
Join:=S2; exit;
end;
if S2=nil then begin
Join:=S1; exit;
end;

p:=Maximum(S1); //找到S1中的最大值p
p^.RightChild:=S2; //S2成为p的右孩子
Join:=p;
End;

11、分离
Procedure Split(x:integer; var S,S1,S2:Tpoint);
Var p:Tpoint;
Begin
p:=Find(x,S); //将x调整为根
S1:=p^.LeftChild; //左孩子为S1
S2:=p^.RightChild; //右孩子为S2
End;

四、时间复杂度分析
由以上这些操作的实现过程可以看出，它们的时间效率完全取决于Splay操作的时间复杂度。下面，我们就用会计方法来分析Splay操作的平摊复杂度。
首先，我们定义一些符号：S(x)表示以结点x为根的子树。|S|表示伸展树S的结点个数。令μ(S) = [log|S|]，μ(x)=μ(S(x))。如图8所示：

图8、符号定义
我们用1元钱表示单位代价（这里我们将对于某个点的访问和旋转看作一个单位时间的代价）。定义伸展树不变量：在任意时刻，伸展树中的任意结点x都至少有μ(x)元的存款。
在Splay调整过程中，费用将会用在以下两个方面：
(1)为使用的时间付费。也就是每一次单位时间的操作，我们要支付1元钱。
(2)当伸展树的形状调整时，我们需要加入一些钱或者重新分配原来树中每个结点的存款，以保持不变量继续成立。

下面我们给出关于Splay操作花费的定理：
定理：在每一次Splay(x,S)操作中，调整树的结构与保持伸展树不变量的总花费不超过3μ(S)+1。

证明：用μ(x)和μ’(x)分别表示在进行一次Zig、Zig-Zig或Zig-Zag操作前后结点x处的存款。下面我们分三种情况分析旋转操作的花费。

情况一、如图9所示：

图9、ZIG
进行Zig或者Zag操作时，为了保持伸展树不变量继续成立，我们需要花费：
μ’(x) +μ’(y) -μ(x) -μ(y) = μ’(y) -μ(x)
≤ μ’(x) -μ(x)
≤ 3(μ’(x) -μ(x))
= 3(μ(S) -μ(x))
此外我们还要花费另外1元钱用来支付访问、旋转的基本操作。因此，一次Zig或Zag操作的花费至多为3(μ(S) -μ(x))。

情况二、如图10所示：

图10、ZIG-ZIG
进行Zig-Zig操作时，为了保持伸展树不变量，我们需要花费：
μ’(x) +μ’(y) +μ’(z) -μ(x) -μ(y) -μ(z) = μ’(y) +μ’(z) -μ(x) -μ(y)
= (μ’(y) -μ(x)) + (μ’(z) -μ(y))
≤ (μ’(x) -μ(x)) + (μ’(x) -μ(x))
= 2 (μ’(x) -μ(x))
与上种情况一样，我们也需要花费另外的1元钱来支付单位时间的操作。
当μ’(x) <μ(x) 时，显然2 (μ’(x) -μ(x)) +1 ≤ 3 (μ’(x) -μ(x))。也就是进行Zig-Zig操作的花费不超过3 (μ’(x) -μ(x))。
当μ’(x) =μ(x) 时，我们可以证明μ’(x) +μ’(y) + μ’(z) <μ(x) +μ(y) +μ(z)，也就是说我们不需要任何花费保持伸展树不变量，并且可以得到退回来的钱，用其中的1元支付访问、旋转等操作的费用。为了证明这一点，我们假设μ’(x) +μ’(y) + μ’(z) >μ(x) +μ(y) +μ(z)。
联系图9，我们有μ(x) =μ’(x) =μ(z)。
那么，显然μ(x) =μ(y) =μ(z)。
于是，可以得出μ(x) =μ’(z) =μ(z)。
令a = 1 + |A| + |B|，b = 1 + |C| + |D|，那么就有：
[log a] = [log b] = [log (a+b+1)]。 ①
我们不妨设b≥a，则有：
[log (a+b+1)] ≥ [log (2a)]
= 1+[log a]
> [log a] ②
①与②矛盾，所以我们可以得到μ’(x) =μ(x) 时，Zig-Zig操作不需要任何花费，显然也不超过3 (μ’(x) -μ(x))。

情况三、与情况二类似，我们可以证明，每次Zig-Zag操作的花费也不超过3 (μ’(x) -μ(x))。

以上三种情况说明，Zig操作花费最多为3(μ(S)-μ(x))+1，Zig-Zig或Zig-Zag操作最多花费3(μ’(x)-μ(x))。那么将旋转操作的花费依次累加，则一次Splay(x,S)操作的费用就不会超过3μ(S)+1。也就是说对于伸展树的各种以Splay操作为基础的基本操作，其平摊时间复杂度都是O(log2n)。所以说，伸展树是一种时间效率非常优秀的数据结构。

【第三部分 伸展树的应用】
伸展树作为一种时间效率很高、空间要求不大、实现又相对简单的数据结构，在解题中大有用武之地。下面就通过一个例子说明伸展树的应用。

例1、营业额统计（Turnover，湖南省队2002年选拔赛)
题目大意：
Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：
该天的最小波动值=min{|该天以前某一天的营业额-该天的营业额|}
当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
注：第一天的最小波动值为第一天的营业额。
数据范围：天数n≤32767，每天的营业额ai≤1,000,000。最后结果T≤231。

初步分析：
题目的意思非常明确，关键是要每次读入一个数，并且在前面输入的数中找到一个与该数相差最小的一个。
我们很容易想到O(n2)的算法：每次读入一个数，再将前面输入的数一次查找一遍，求出与当前数的最小差值，记入总结果T。但由于本题中n很大，这样的算法是不可能在时限内出解的。而如果使用线段树记录已经读入的数，就需要记下一个2M的大数组，这在当时比赛使用TurboPascal 7.0编程的情况下是不可能实现的。而前文提到的红黑树与平衡二叉树虽然在时间效率、空间复杂度上都比较优秀，但过高的编程复杂度却让人望而却步，于是我们想到了伸展树算法。

算法描述：
进一步分析本题，解题中，涉及到对于有序集的三种操作：插入、求前趋、求后继。而对于这三种操作，伸展树的时间复杂度都非常优秀，于是我们设计了如下算法：
开始时，树S为空，总和T为零。每次读入一个数p，执行Insert(p,S)，将p插入伸展树S。这时，p也被调整到伸展树的根结点。这时，求出p点左子树中的最右点和右子树中的最左点，这两个点分别是有序集中p的前趋和后继。然后求得最小差值，加入最后结果T。

解题小结：
由于对于伸展树的基本操作的平摊复杂度都是O(log n)的，所以整个算法的时间复杂度是O(nlog n)，可以在时限内出解。而空间上，可以用数组模拟指针存储树状结构，这样所用内存不超过400K，在TP中使用动态内存就可以了。编程复杂度方面，伸展树算法非常简单，程序并不复杂。虽然伸展树算法并不是本题唯一的算法，但它与其他常用的数据结构相比还是有很多优势的。下面的表格就反映了在解决这一题时各个算法的复杂度。从中可以看出伸展树在各方面都是优秀的，这样的算法很适合在竞赛中使用。

顺序查找
线段树
AVL树
伸展树
时间复杂度
O(n2)
O(nlog2a)
O(nlog2n)
O(nlog2n)
空间复杂度
O(n)
O(a)
O(n)
O(n)
编程复杂度
很简单
较简单
较复杂
较简单

【第四部分 总结】
由上面的分析介绍，我们可以发现伸展树有以下几个优点：
1、时间复杂度低。伸展树的各种基本操作的平摊复杂度都是O(log2n)的。在树状数据结构中，无疑是非常优秀的。
2、空间要求不高。与红黑树需要记录每个结点的颜色、AVL树需要记录平衡因子不同的是，伸展树不需要记录任何信息以保持树的平衡。
3、算法简单，编程容易。伸展树的基本操作都是以Splay操作为基础的，而Splay操作中只需根据当前结点的位置进行旋转操作即可。
虽然伸展树算法与AVL树在时间复杂度上相差不多，甚至有时候会比AVL树慢一些，但伸展树的编程复杂度大大低于AVL树。在竞赛中，使用伸展树在编程和调试中都更有优势。
所以，在信息学竞赛中，不能只是一味的追求算法有很高的时间效率，而需要在时间复杂度、空间复杂度、编程复杂度三者之间找到一个“平衡点”，合理的选择算法。这也需要我们在平时对各种算法反复琢磨，深入研究，在竞赛中才能够游刃有余的应用。

【附录】
1、文中提到的伸展树的基本操作，具体过程可参照动画：Splay Tree.htm。
2、讲座课件见：Splay Tree.ppt。
3、针对文中例题，用伸展树算法编写的程序：Turnover.pas。
Program Turnover_SplayTree_FP;
Const
inf='turnover.in';
outf='turnover.out';
maxn=32767;

Type
Tp=record //树的结点
data:longint; //营业额
father,left,right:integer;
end;

Var
n,now, //总天数、当前天数
root, //伸展树根
prev,next, //前趋、后继
same:integer; //当天营业额相同的
min:longint; //最小差值
ans:extended; //答案
tree:array[0..maxn]of Tp;

procedure init; //初始化树，输入
begin
fillchar(tree,sizeof(tree),0);
read(n); //输入天数
read(tree[1].data);
root:=1;
ans:=tree[1].data;
end;

procedure leftrotate(x:integer); //左旋
var y:integer;
begin
y:=tree[x].father;

tree[y].right:=tree[x].left;
if tree[x].left<>0
then tree[tree[x].left].father:=y;

tree[x].father:=tree[y].father;
if tree[y].father<>0 then begin
if y=tree[tree[y].father].left
then tree[tree[y].father].left:=x
else tree[tree[y].father].right:=x;
end;
tree[y].father:=x;
tree[x].left:=y;
end;

procedure rightrotate(x:integer); //右旋
var y:integer;
begin
y:=tree[x].father;

tree[y].left:=tree[x].right;
if tree[x].right<>0
then tree[tree[x].right].father:=y;

tree[x].father:=tree[y].father;
if tree[y].father<>0 then begin
if y=tree[tree[y].father].left
then tree[tree[y].father].left:=x
else tree[tree[y].father].right:=x;
end;

tree[y].father:=x;
tree[x].right:=y;
end;

procedure splay(now:integer); //伸展操作
var t:integer;
begin
while tree[now].father<>0 do
begin
t:=tree[now].father;

if tree[t].father=0 then begin
if now=tree[t].left
{ZIG} then rightrotate(now)
{ZAG} else leftrotate(now);
break;
end;

if now=tree[t].left then begin
if t=tree[tree[t].father].left then begin
{ZIG-ZIG} rightrotate(t);
rightrotate(now);
end
else begin
{ZIG-ZAG} rightrotate(now);
leftrotate(now);
end;
end
else begin
if t=tree[tree[t].father].right then begin
{ZAG-ZAG} leftrotate(t);
leftrotate(now);
end
else begin
{ZAG-ZIG} leftrotate(now);
rightrotate(now);
end;
end;
end;

root:=now;
end;

procedure insert; //插入
var t:integer;
begin
t:=root; same:=now;
while true do
begin
if tree[t].data=tree[now].data
then begin min:=0; same:=t; exit; end;
if tree[t].data>tree[now].data then begin
if tree[t].left=0 then begin
tree[now].father:=t;
tree[t].left:=now;
exit;
end
else t:=tree[t].left;
end
else begin
if tree[t].