Splay Tree 重复次数mul以及一些进阶操作

Posted on 2011-06-21 11:31 Mato_No1 阅读(506) 评论(0)  编辑 收藏 引用 所属分类: 平衡树
额……最近两天光顾着刷题忘了总结了……正好现在把总结的东东全部补上吧囧……

【重复次数mul】
在前面第一篇总结Splay Tree的时候就提到了结点的重复次数(mul)域,这个东东至今在网上还米看见有犇用(在本沙茶见过的范围内),但是不可否认的是这个域在某些情况下几乎是“必须使用”的。
所谓重复次数,就是将树中所有值(v)相同的结点全部合并成一个,这些结点的总个数就是合并后的结点的mul值。比如,在一棵空树中插入3个值为5的结点后,在使用mul域的情况下,树中只有一个结点,其v值为5,mul值为3。
在平衡树中,值相同的结点确实非常碍事。按照二叉查找树的定义:“要么是一棵空树,要么是一棵满足以下条件的非空树:根结点左子树中所有结点的值均小于根结点,根结点右子树中所有结点的值均大于根结点,且根的左右子树均为二叉查找树”,在二叉查找树中,是不应该出现值相同的结点的。可是在实际问题中,出现值相同的结点几乎是不可避免的。此时,树的定义就会变得非常模糊,也就是要把二叉查找树定义中的“小于”全部改为“小于等于”,“大于”全部改为“大于等于”。这样定义的树在一般情况下也米有神马问题,但是在找前趋(Pred)和找后继(Succ)操作中,问题就来了。因为根结点的前趋和后继的值可能与根结点相等(比如 HNOI2004 宠物收养所 那一题),这时,根结点的前趋既有可能在左子树里,也有可能在右子树里,根结点的后继也一样。此时,这两个操作就无法进行了。
【mul域的维护】
mul域其实可以看成结点的一个本身属性,和v一样。因此在旋转、伸展操作中任何结点的mul值都是不会改变的。可能改变结点mul值的地方只有两处:一是插入,二是删除。在插入一个值为_v的结点的时候,如果发现值为_v的结点在树中已经存在,则只会将这个结点的mul值加1,而不是真正插入一个新的结点。同样的,在删除一个结点的时候,如果这个结点的mul值大于1,则只会将这个结点的mul值减1,而不是真正删除。
【mul域的作用】
mul域最主要的作用就是解决值相同的结点对于某些操作的影响。另外,mul域的引入可以减少树中结点的总个数(尤其是当插入的结点数很多而结点的值的范围不大的时候),从而降低时间复杂度(准确来说可以降低常数)。
【Splay Tree的进阶操作】
<1>找非根结点的前趋和后继。
Splay Tree由于有伸展操作,可以将要求前趋或后继的点伸展到根再求前趋或后继。如果要不通过伸展操作找一个非根结点的前趋或后继怎么办?
设这个结点为x。如果x有左子结点,则x的前趋就是x的左子结点的右链上的最后一个结点;如果x没有左子结点,则x的前趋就是从x开始往上(往x的祖先)查找,直到找到第一个是其父结点的右子结点的结点为止,则这个结点的父结点就是x的前趋(或者说,就是不断沿着x的父结点往上找,一开始都是往右的,找到第一个往左的就行了)。后继则正好相反。证明可以用中序遍历。
<2>找某个值v0的前趋和后继(值为v0的结点在树中不一定存在)。
所谓v0的前趋和后继,就是指在树中值小于(也有的是不大于)v0的最大的结点的值,和树中值大于(也有的是不小于)v0的最小的结点的值。在有了操作(1)【不通过伸展操作找非根结点的前趋和后继】以后,这个操作变得极为容易:先进行普通的查找操作(查找值为v0的结点),如果能找到,则剩下的步骤就和操作(1)一样了;如果找不到,则必然是找到某个空结点(0)处,假设在这里插入一个值为v0的结点(只是假设,不是真插入),则该结点显然是没有左子结点的,因此就是“从该结点开始往上查找,直到找到第一个是其父结点的右子结点的结点为止,则这个结点的父结点就是该结点的前趋”,也就是v0的前趋;后继类似。
在查找过程中可以进行一个常数优化:设点i为查找过程中“右转”的最后一个结点(即找到该结点后,接下来是该结点的右子结点),每次往右子结点转的时候就更新i,则最后结点i就是值v0的前趋;后继类似。
<3>删除所有值在某区间内的结点(这个区间可以是开区间、闭区间或半开半闭区间)。
以开区间为例:删除树中所有值在(l, r)范围内的结点。先找到l的前趋P和r的后继S(注意这里的前趋和后继是包括“等于”的),然后将P伸展到根,S伸展到P的右子结点处,则S的左子树中就是所有值在(l, r)范围内的结点,直接删掉这棵子树即可(注意删除后要更新S和P);若改为闭区间,则将前趋和后继中的“等于”去掉(即必须是小于或大于);半开半闭区间则一半按开区间处理,一半按闭区间处理。问题是,如果点P或点S不存在怎么办。有两种解决办法,一是若P和S之一存在,则将其伸展到根,然后直接删掉其左子树或右子树即可;若P和S都不存在,则树为空,直接将root置为0即可;二是按照sequence的办法,加入两个边界结点,当前趋或后继不存在时就认为是边界结点。
其实不光是删除,在找到了这棵子树后可以对它进行一些整体操作,从而让Splay Tree具有线段树的功能(这个在下面的NOI2005 sequence那一题里面会总结)。
<4>插入一棵树(当然这棵树也是Splay Tree,并且原树中的结点值序列与新树中的结点值序列不相交)。
有时候,题目中会连续出现很多插入操作,中间没有其它操作,此时,与其一个一个插入,还不如将它们先建成一棵树(建树的方法在下一篇里总结),再整体插入。整体插入的方法:设L和R分别是新树里值最小的结点和值最大的结点,在原树中找到L的前趋P和R的后继S,将P伸展到根,S伸展到P的右子结点处,由于原树中的结点值序列与新树中的结点值序列不相交(也就是原树中的结点值要么小于L的值,要么大于R的值),因此S无左子结点,此时将新树作为S的左子树即可。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理