splay树及其应用

《splay树及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Splay树及其应用Yali朱全民二叉查找树二叉查找树(BinarySearchTree)可以被用来表示有序集合、建立索引或优先队列等。最坏情况下，作用于二叉查找树上的基本操作的时间复杂度，可能达到O(n)。某些二叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、AVL树等。Splay树Splay树是二叉查找树的改进。对Splay树的操作的均摊复杂度是O(log2n)。Splay树与二叉查找树一样，也具有有序性。即Splay树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。Splay树的核

2、心思想就是通过Splay操作进行自我调整，从而获得平摊较低的时间复杂度。Splay操作Splay操作是在保持Splay树有序性的前提下，通过一系列旋转操作将树中的元素x调整至树的根部的操作(Zig:右旋,Zag:左旋)。在旋转的过程中，要分三种情况分别处理：1)Zig或Zag2)Zig-Zig或Zag-Zag3)Zig-Zag或Zag-ZigSplay操作情况1Zig或Zag操作：节点x的父节点y是根节点。Splay操作情况2Zig-Zig或Zag-Zag操作：节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右

3、孩子。Spaly操作情况3Zig-Zag或Zag-Zig操作：节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。Splay操作举例Splay(1,S)Spaly树基本操作查找：与二叉排序树查找类似，只是查找结束后要将找到的元素通过Splay操作旋转到根。插入：用查找过程找到要插入的位置，进行插入。然后将新元素旋转到根。删除：首先在树中找到要删除的元素，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素转到根，由于它是左子树中的最大元素，所以他不存在有儿子，这样只要把原

4、来的右子树作为他的右子树，就重新合并成了一棵树。可见在Splay树的基本操作中，处处要用到Splay旋转操作！例一Pet（湖南省省队选拔赛）宠物收养场提供两种服务：收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养人/遗弃宠物过多，则当前来的宠物/领养人选择离其特点值最近的（如果有两个特点值与其同样接近，则选择较小的）领养人/宠物，被领养/领养。并且纪录两个特点值的差值。输入N条请求(X,Y)，X=0表示宠物;X=1表示领养人，Y为特征值。任务是计算所有差值的和。（N<=80000，等待的宠物

5、/领养者数M<=10000）例一Pet我们先用最普通的数组记录过多的宠物/领养人。查找：需要检索整个数组，复杂度为O(M)删除：删除指定元素之后，需要成批移动主轴元素，时间复杂度也为O(M)这样最坏情况下时间复杂度为O(NM)，是不可取的。例一Pet对宠物/领养人过多的情况下，我们建立一颗排序二叉树，并记录其属性Sign（宠物/领养人）。对于命令(X,Y)，如果树为空或者X=Sign，则将其插入，并令Sign=x；否则在树中查找符合要求的结点，记录特征值之差，并将其删除。（注意无论树的属性是0或1,相对进行的操作是相同的）普通的排序二叉树在最坏

6、情况下时间复杂度也是O(NM)。我们可以应用较高效的排序二叉树，例如AVL树（平衡二叉树）或者Splay树。例一PetAVL树引入平衡因子的概念，使得整棵排序二叉树严格平衡，时间复杂度严格为O(nlogm)。但是其编程复杂度很高。Splay树通过Splay旋转操作，使得分摊时间复杂度为O(nlogm)，虽然常系数较AVL树相比大。但是操作简便，编程复杂度较低。在考场上我们要综合考虑各方面的因素，合理的选择数据结构。例二郁闷的出纳员(NOI2004)你是一个公司出纳员，需要处理n条下面的命令：此外，如果某个员工的工资低于最低工资下界Min，他就会

7、立刻离开公司。现在请你写一个程序完成这个工资统计的工作。名称格式作用I命令I_k新建一个工资档案，初始工资为k。A命令A_k把每位员工的工资加上kS命令S_k把每位员工的工资扣除kF命令F_k查询第k多的工资例二郁闷的出纳员这个题目简单来说就是请你设计一种数据结构满足如下4种操作：向集合中插入一个数；将集合中所有的数都加上一个值；将集合中所有的数都减去一个值，并将所有低于min的数从集合中删除掉（min是事先给定的一个固定的数）；查找集合中第k大的数。我们考虑应用Splay树维护这个工资系统。例二郁闷的出纳员Splay树的插入、删除、查找第K大

8、元素都可以在均摊时间复杂度O(logn)内完成。但是还有一种操作就是将集合内的所有元素都加上或减去一个值，如果单纯的按照题目要求对数据进行改动，则每一