国家集训队2004论文集 杨思雨

《国家集训队2004论文集 杨思雨》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、伸展树的基本操作与应用芜湖一中杨思雨1引言二叉查找树(BinarySearchTree)可以被用来表示有序集合、建立索引或优先队列等。最坏情况下，作用于二叉查找树上的基本操作的时间复杂度，可能达到O(n)。某些二叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、AVL树等。2伸展树伸展树(SplayTree)是二叉查找树的改进。对伸展树的操作的平摊复杂度是O(log2n)。伸展树的空间要求、编程难度非常低。3伸展树伸展树与二叉查找树一样，也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右

2、子树中的每一个元素都大于x。伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)4伸展操作Splay(x,S)伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树S中的元素x调整至树的根部的操作。在旋转的过程中，要分三种情况分别处理：1)Zig或Zag2)Zig-Zig或Zag-Zag3)Zig-Zag或Zag-Zig5伸展操作Splay(x,S)情况1Zig或Zag操作：节点x的父节点y是根节点。6伸展操作Splay(x,S)情况2Zig-Zig或Zag-Zag操作：节点x的父节点y不是根节点，且

3、x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。7伸展操作Splay(x,S)情况3Zig-Zag或Zag-Zig操作：节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。8伸展操作举例Splay(1,S)9伸展树的基本操作求前趋求后继合并分离查找插入删除求最大值求最小值伸展操作是基础！10时间复杂度分析S(x)表示以x为根的子树

4、S

5、表示树S的节点个数令μ(S)=[log2

6、S

7、]([]表示取下整)μ(x)=μ(S(x))11时间复杂度分析用1元钱表示一个单位时间代价。伸展树不变量：在任意

8、时刻，伸展树中的任意节点x都至少有μ(x)元的存款。对某个节点的访问和旋转—会计方法12时间复杂度分析在Splay调整过程中，费用将会用在以下两个方面：(1)为使用的时间付费。也就是每一次单位时间的操作，要支付1元钱。(2)当伸展树的形状调整时，需要加入一些钱或者重新分配原来树中每个节点的存款，以保持不变量继续成立。13时间复杂度分析用μ(x)和μ’(x)分别表示在进行一次旋转操作前后节点x处的存款。分三种情况分析旋转操作的花费：(1)Zig或Zag(2)Zig-Zig或Zag-Zag(3)Zig-Zag或Zag-Zig14时间复杂度分

9、析情况1Zig或Zag为了保持伸展树不变量继续成立，需要花费：此外我们花费另外1元钱用来支付访问、旋转的基本操作。所以，一次Zig或Zag操作的花费至多为3(μ(S)-μ(x))+115时间复杂度分析情况2Zig-Zig或Zag-Zag为了保持不变量，需要花费：与情况1一样，也需要花费另外的1元钱来支付单位时间的操作。16时间复杂度分析情况2Zig-Zig或Zag-Zag当μ’(x)<μ(x)时，显然2(μ’(x)-μ(x))+1≤3(μ’(x)-μ(x))也就是进行Zig-Zig操作的花费不超过3(μ’(x)-μ(x))当μ’(x)=

10、μ(x)时，可以证明：μ’(x)+μ’(y)+μ’(z)<μ(x)+μ(y)+μ(z)也就是说我们不需要任何花费保持伸展树不变量，并且可以得到退回来的钱，并用其中的1元支付单位操作的费用。一次Zig-Zig或Zag-Zag的花费至多为3(μ’(x)-μ(x))17时间复杂度分析情况3Zig-Zag或Zag-Zig与情况2相似，可以证明一次Zig-Zag或Zag-Zig操作的花费至多为3(μ’(x)-μ(x))18时间复杂度分析ZigZig-ZigZig-Zag3(μ(S)-μ(x))+13(μ’(x)-μ(x))3(μ’(x)-μ(x)

11、)Splay(x,S)3(μ(S)-μ(x))+1O(log2n)基本操作19伸展树的应用营业额统计Turnover(HNTSC-02)分析公司的营业情况是一项相当复杂的工作。经济管理学上定义了一种最小波动值来衡量营业情况：每天的最小波动值=min{

12、该天以前某一天的营业额-该天的营业额

13、}第一天的最小波动值为第一天的营业额。现在给出公司成立以来每天的营业额，编写一个程序计算公司成立以来每天的最小波动值的总和。数据范围：天数n≤32767，每天的营业额ai≤1,000,000。最后结果T≤231。例题描述20伸展树的应用本题的关键是要每

14、次读入一个数，并且在前面输入的数中找到一个与该数相差最小的一个。顺序查找前面输入的数用线段树记录输入的数红黑树或平衡二叉树初步分析时间复杂度O(n2)，不能在时限内出解空间要求很大，需要一个大数组编程太复杂