Splay树及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Splay,树及其应用,Yali,朱全民,二叉查找树,二叉查找树,(,Binary Search Tree),可以被用来表示有序集合、建立索引或优先队列等。,最坏情况下，作用于二叉查找树上的基本操作的时间复杂度，,可能达到,O(n,)。,某些二,叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、,AVL,树,等。,Splay,树,Splay,树,是二叉查找树的改进。,对,Splay,树的操作的均摊复杂度是,O(log,2,n),。,Splay,树与二叉查找树一样，也具有,有序性,。,即,Splay树中的每一个节点,x,都满足：该节点左子树中的每一个元素都小于,x,，而其右子树中的每一个元素都大于,x,。,Splay,树的核心思想就是通过,Splay,操作进行,自我调整,，从而获得平摊较低的时间复杂度。,Splay,操作,Splay,操作,是在保持,Splay,树有序性的前提下，通过一系列旋转操作将树中的元素,x,调整至树的根部的操作,(,Zig,:,右旋,Zag,:,左旋,),。,在旋转的过程中，要分三种情况分别处理：,1),Zig,或,Zag,2)Zig-Zig,或,Zag-Zag,3)Zig-Zag,或,Zag-Zig,Splay,操作 情况,1,Zig,或,Zag,操作：,节点x,的父节点,y,是根节点。,Splay,操作,情况,2,Zig-Zig,或,Zag-Zag,操作：,节点,x,的父节点,y,不是根节点，且,x,与,y,同时是各自父节点的左孩子或者同时是各自父节点的右孩子。,Spaly,操作 情况,3,Zig-Zag,或,Zag-Zig,操作：,节点,x,的父节点,y,不是根节点，,x,与,y,中一个是其父节点的左孩子而另一个是其父节点的右孩子。,Splay,操作举例,Splay(1,S),Spaly,树基本操作,查找：与二叉排序树查找类似，只是查找结束后要将找到的元素通过,Splay,操作旋转到根。,插入：用查找过程找到要插入的位置，进行插入。然后将新元素旋转到根。,删除：首先在树中找到要删除的元素，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素转到根，由于它是左子树中的最大元素，所以他不存在有儿子，这样只要把原来的右子树作为他的右子树，就重新合并成了一棵树。,可见在,Splay,树的基本操作中，处处要用到,Splay,旋转操作！,例一,Pet,（湖南省省队选拔赛）,宠物收养场提供两种服务：收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养人,/,遗弃宠物过多，则当前来的宠物,/,领养人选择离其特点值最近的（如果有两个特点值与其同样接近，则选择较小的）领养人,/,宠物，被领养,/,领养。并且纪录两个特点值的差值。,输入,N,条请求,(X,Y),，,X=0,表示宠物,;X=1,表示领养人，,Y,为特征值。,任务是计算所有差值的和。,（,N=80000,，等待的宠物,/,领养者数,M=10000,）,例一,Pet,我们先用最普通的数组记录过多的宠物,/,领养人。,查找：需要检索整个数组，复杂度为,O(M),删除：删除指定元素之后，需要成批移动主轴元素，时间复杂度也为,O(M),这样最坏情况下时间复杂度为,O(NM),，是不可取的。,例一,Pet,对宠物,/,领养人过多的情况下，我们建立一颗排序二叉树，并记录其属性,Sign,（宠物,/,领养人）。,对于命令,(X,Y),，如果树为空或者,X=Sign,，则将其插入，并令,Sign=x,；,否则在树中查找符合要求的结点，记录特征值之差，并将其删除。（注意无论树的属性是,0,或,1,相对进行的操作是相同的）,普通的排序二叉树在最坏情况下时间复杂度也是,O(NM),。我们可以应用较高效的排序二叉树，例如,AVL,树（平衡二叉树）或者,Splay,树。,例一,Pet,AVL,树引入平衡因子的概念，使得整棵排序二叉树严格平衡，时间复杂度严格为,O(nlogm,),。但是其编程复杂度很高。,Splay,树通过,Splay,旋转操作，使得分摊时间复杂度为,O(nlogm,),，虽然常系数较,AVL,树相比大。但是操作简便，编程复杂度较低。,在考场上我们要综合考虑各方面的因素，合理的选择数据结构。,例二 郁闷的出纳员,(NOI2004),你是一个公司出纳员，需要处理,n,条下面的命令：,此外，如果某个员工的工资低于最低工资下界,Min,，他就会立刻离开公司。,现在请你写一个程序完成这个工资统计的工作。,名称,格式,作用,I,命令,I,_k,新建一个工资档案，初始工资为,k,。,A,命令,A,_k,把每位员工的工资加上,k,S,命令,S,_k,把每位员工的工资扣除,k,F,命令,F,_k,查询第,k,多的工资,例二 郁闷的出纳员,这个题目简单来说就是请你设计一种数据结构满足如下,4,种操作：,向集合中插入一个数；,将集合中所有的数都加上一个值；,将集合中所有的数都减去一个值，并将所有低于,min,的数从集合中删除掉（,min,是事先给定的一个固定的数）；,查找集合中第,k,大的数。,我们考虑应用,Splay,树维护这个工资系统。,例二 郁闷的出纳员,Splay,树的插入、删除、查找第,K,大元素都可以在均摊时间复杂度,O(logn,),内完成。,但是还有一种操作就是将集合内的所有元素都加上或减去一个值，如果单纯的按照题目要求对数据进行改动，则每一步这样的操作所需的时间复杂度为,O(NlogN,),（因为需要重建二叉树）,例二 郁闷的出纳员,注意到，这个增值操作不会改变已经在树中的元素的大小关系，只会改变已经在集合内的元素与以后将要加进来的元素间的关系。这样我们就可以只改变以后要加进来的元素而不改变当前已有的元素。,具体做法为设立一个表示改变量的变量,delta,，遇到改值操作，只需令,delta=,delta,+a,，同时将,Splay,树中所有小于,min-delta,的元素删掉。,当新增一个值为,x,的元素时，只需先修改为,x-delta,在插入树中即可。这样改值的复杂度就为,O(1),了,例二 郁闷的出纳员,通过,Splay,树维护工资系统，我们得到了时间复杂度为,O(nlogn,),的算法。,至此，问题得到解决。,例三 序列终结者,给定一个长度为,N,的序列，每个序列的元素是一个整数。要支持以下三种操作：,将,L,R,这个区间内的所有数加上,V,。,将,L,R,这个区间翻转，比如,1 2 3 4,变成,4 3 2 1,。,求,L,R,这个区间中的最大值。,最开始所有元素都是,0,。,N=50000,，操作数,=100000,。,例三 序列终结者,我们将序列的每个元素值作为关键字，将它们在序列中的相对位置作为判定大小关系的函数（左小右大），这样就可以建立一棵,n,个节点的,Splay,树。,我们给,Splay,树增添三个域：,Treev.Add,：记录以节点,v,为根的子树被整体改值的情况。,Treev.Turn,：记录以节点,v,为根的子树所表示的这段区间有没有被整体翻转过。,Treev.Sum,：记录以节点,v,为根的子树中的最大值。,三个序列操作都和某一段给定区间,L,R,有关，所以我们首先介绍区间的截取操作。,例三 序列终结者,首先我们找到,Splay,中的第,L,大的元素，将它旋转到根，将并将它的左子树分离出来。设原树是,T1,，它的左子树是,T2,则现在的,Splay,树,T2,就是序列,1,L-1,所代表的树；,T1,就是序列,L,n,所代表的树。,同理，找到,T1,中第,R-L+1,大的元素，将它旋转到根，并将,T1,的右子树分离出来，设为,T3,。,则现在,T1,就是序列,L,R,所代表的树，,T3,就是序列,R1,n,所代表的树。,例三 序列终结者,这样我们就成功分离出,L,R,区间，并且在效率上相当于只用了常数次的查找操作。,这是我们只需要对,T1,的根节点进行修改,Sum,、,Add,或者,Turn,域的修改即可。,修改完后，再将,T1,、,T2,、,T3,进行合并，易知合并在效率上也相当于常数次的查找操作。,所以对于序列的每一种操作，都可以在均摊复杂度,O(logn,),完成。,例三 序列终结者,现在的问题是，修改了某一个子树的,Sum,、,Add,、,Turn,值之后，以后在进行查找、旋转等操作的时候怎样处理和运用？,我们可以在查找到某个节点,v,的时候，将它的,Sum,、,Add,、,Turn,值传递到子树上，这样就不影响后面的操作了。,例三 序列终结者,这里以修改,Add,为例。当查找到节点,p,时，进行如下操作：,p.data,p.data+p.add,；,p.lch.add,p.lch.add+p.add,；,p.rch.add,p.rch.add+p.add,；,/,将,p,节点的,add,值 分散到左右子树和,p,节点的,data,中,p.add,0,；,/,清空,add,域,Sum,、,Turn,域的修改也可以类似进行。,例三 序列终结者,综合上面的分析，我们可以在,O(mlogn,),的时间复杂度内解决序列操作的问题。,至此问题得到解决。,