算法合集之伸展树的基本操作与应用.pptx

《算法合集之伸展树的基本操作与应用.pptx》由会员分享，可在线阅读，更多相关《算法合集之伸展树的基本操作与应用.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1伸展树伸展树(Splay Tree)是二叉查找树的改进。对伸展树的操作的平摊复杂度是O(log2n)。伸展树的空间要求、编程难度非常低。第1页/共35页2伸展树伸展树与二叉查找树一样，也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。伸展树可以自我调整，这就要依靠 第2页/共35页3伸展操作Splay(x,S)伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树S中的元素x调整至树的根部的操作。在旋转的过程中，要分三种情况分别处理：1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag

2、3)Zig-Zag 或 Zag-Zig 第3页/共35页4伸展操作Splay(x,S)情况1Zig或Zag操作：节点x的父节点y是根节点。第4页/共35页5伸展操作Splay(x,S)情况2Zig-Zig或Zag-Zag操作：节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。第5页/共35页6伸展操作Splay(x,S)情况3Zig-Zag或Zag-Zig操作：节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。第6页/共35页7伸展操作举例Splay(1,S)第7页/共35页8伸展树的基本操作求前趋 求后继合并分离查找

3、插入删除 求最大值求最小值伸展操作是基础！第8页/共35页9时间复杂度分析S(x)表示以x为根的子树|S|表示树S的节点个数令(S)=log2|S|(表示取下整)(x)=(S(x)第9页/共35页10时间复杂度分析用1元钱表示一个单位时间代价。伸展树不变量：在任意时刻，伸展树中的任意节点x都至少有(x)元的存款。对某个节点的对某个节点的访问和旋转访问和旋转会计方法第10页/共35页11时间复杂度分析在Splay调整过程中，费用将会用在以下两个方面：(1)为使用的时间付费为使用的时间付费。也就是每一次单位时间的操作，要支付1元钱。(2)当伸展树的形状调整时，需要加入一些钱或者重新分配原来树中每个

4、节点的存款，以保持不变量继续成保持不变量继续成立立。第11页/共35页12时间复杂度分析用(x)和(x)分别表示在进行一次旋转操作前后节点x处的存款。分三种情况分析旋转操作的花费：(1)Zig 或 Zag (2)Zig-Zig 或 Zag-Zag (3)Zig-Zag 或 Zag-Zig 第12页/共35页13时间复杂度分析 情况1Zig或Zag为了保持伸展树不变量继续成立，需要花费：此外我们花费另外1元钱用来支付访问、旋转的基本操作。所以，一次Zig或Zag操作的花费至多为3(S)-(x)+1第13页/共35页14时间复杂度分析 情况2Zig-Zig或Zag-Zag为了保持不变量，需要花费：

5、与情况1一样，也需要花费另外的1元钱来支付单位时间的操作。第14页/共35页15时间复杂度分析 情况2Zig-Zig或Zag-Zag当(x)(x)时，显然2(x)-(x)+1 3(x)-(x)也就是进行Zig-Zig操作的花费不超过3(x)-(x)当(x)=(x)时，可以证明：(x)+(y)+(z)(x)+(y)+(z)也就是说我们不需要任何花费保持伸展树不变量，并且可以得到退回来的钱，并用其中的1元支付单位操作的费用。一次Zig-Zig或Zag-Zag的花费至多为3(x)-(x)第15页/共35页16时间复杂度分析 情况3Zig-Zag或Zag-Zig 与情况2相似，可以证明 一次Zig-Z

6、ag或Zag-Zig操作的花费至多为3(x)-(x)第16页/共35页17时间复杂度分析ZigZig-ZigZig-Zag3(S)-(x)+13(x)-(x)3(x)-(x)Splay(x,S)3(S)-(x)+1O(log2n)基本操作第17页/共35页18伸展树的应用 营业额统计Turnover(HNTSC-02)分析公司的营业情况是一项相当复杂的工作。经济管理学上定义了一种最小波动值来衡量营业情况：每天的最小波动值=min|该天以前某一天的营业额-该天的营业额|第一天的最小波动值为第一天的营业额。现在给出公司成立以来每天的营业额，编写一个程序计算公司成立以来每天的最小波动值的总和。数据范

7、围：天数n32767，每天的营业额ai1,000,000。最后结果T231。例题描述第18页/共35页19伸展树的应用本题的关键是要每次读入一个数，并且在前面输入的数中找到一个与该数相差最小的一个。顺序查找前面输入的数用线段树记录输入的数红黑树或平衡二叉树初步分析时间复杂度O(n2)，不能在时限内出解空间要求很大，需要一个大数组编程太复杂，调试不方便第19页/共35页20伸展树的应用每次读入一个数p，将p插入伸展树S，同时p也被调整到伸展树的根节点。求出p点左子树中的最大值和右子树中的最小值，这两个数就分别是有序集中p的前趋和后继。进而求得最小差值，加入最后结果T。算法描述l这题中，涉及到对于

8、有序集的三种操作：插入、求前趋、求后继第20页/共35页21伸展树的应用使用伸展树算法解决本题，时间复杂度为O(nlog2n)，空间要求不大，编程和调试也都非常容易。下面的表格对几种算法做出了比较：顺序查找线段树AVL树伸展树时间复杂度O(n2)O(nlog2a)O(nlog2n)O(nlog2n)空间复杂度O(n)O(a)O(n)O(n)编程复杂度很简单较简单较复杂较简单解题小结第21页/共35页22总结伸展树有以下三个优点：1)时间复杂度低，伸展树的各种基本操作的平摊复杂度都是O(log2n)的。2)空间要求不高，伸展树不需要记录任何信息以保持树的平衡。3)算法简单。编程容易，调试方便。第22页/共35页23总结在信息学竞赛中，我们不能一味的追求算法有很高的时间效率，而应该合理的选择算法，找到时间复杂度、空间复杂度、编程复杂度三者之间的平衡点反复琢磨多做比较灵活应用第23页/共35页24第24页/共35页25希望能和大家多希望能和大家多交流交流E-m a i l:D e a d F i s h Y S Y 1 6 3.c o m第25页/共35页35感谢您的观看！第35页/共35页