The-Magical-Splay

神奇的SplayTheMagicalSplayAproductofsqybi神奇的Splay(TheMagicalSplay)Aproductofsqybi1关键字伸展树Splay摘要引言部分介绍了平衡二叉树的一些基本知识。基本操作部分介绍了Splay的两个十分简单的操作，即旋转与伸展操作。它们是其它操作的基础。进阶操作部分介绍了一些比较常用的操作。特殊操作部分介绍了一些利用了Splay特性或Splay特有的操作。广泛应用部分通过几个例子使读者了解Splay的一些很奇特的应用。说明本文旨在帮助对平衡二叉树有所了解但不熟悉的OIer了解Splay。关于内部版：未经许可，请不要以任何形式传播给任何人！关于其他版本：不基于任何协议发布，但可以在署名的情况下以各种形式对此作品进行非商业性的复制传播。联系方式E-mail:[e-mail]:欢迎大家找到文章中的各类bug（包括描述错误，各种科学性错误，错别字，伪代码错误，字体错误等各种可能影响阅读的问题）并与本人联系。另：文章中引用了一些论文、题目等资料，如果你认为本文引用的某些资料侵犯了你的权益，也请与本人联系。神奇的Splay(TheMagicalSplay)Aproductofsqybi2引言伸展树是平衡二叉树的一种。普通的二叉搜索树在一些特殊数据下会退化成链状，不能保证均摊O(nlogn)的复杂度，平衡二叉树则通过一些条件下的旋转操作保证了O(nlogn)的复杂度；而Splay则通过其特殊的伸展（Splay）操作保证了均摊．．复杂度为O(nlogn)。两类平衡二叉树竞赛中经常见到的平衡二叉树有两类，一类是严格维护平衡的，可以保证每次操作的复杂度严格为O(logn)，例如AVL，SBT等；另一类是非严格维护平衡的，但每次操作均摊复杂度为O(logn)，例如Treap，Splay等。虽然第二种平衡二叉树的速度有可能会慢一些，但这并不会影响太多。Splay的优势Splay作为竞赛中常用的最灵活的平衡二叉树，有着许多先天的优势。而这些优势，都是和Splay的灵活分不开的。其中一些虽然Treap靠更改附加域也可以做到，但Splay的原生支持显然更好用些。首先，Splay不需要任何附加空间。它既不需要像SBT一样维护size域（即使size域在大多数情况下对于任何平衡二叉树都很有用，不过不排除某些情况下size域是不必要的），也不需要像Treap一样维护一个随机数。其次，Splay的维护平衡很自然。不需要任何过多的比较，只需要每次访问到某个叶子节点之后将它旋转到根，伸展操作与其他操作一气呵成。再次，Splay支持的操作更多。比如删除数据结构中比某个值大的所有数，用其它平衡二叉树只能一个一个删掉，时间复杂度为O(klogn)；而Splay可以在O(logn)的复杂度完成这个操作。最后，Splay能够解决的问题更广泛。在某些问题中，Splay甚至可以替代块状链表维护一个序列！这也正是本文将它称作“TheMagicalSplay”的原因。Splay的不足Splay的不足似乎不是那么明显，除了速度是以上提到的几个平衡二叉树中最慢的一个。但要知道的是，这只是常数上的差异。也就是说，Splay虽然可以被构造数据导致速度变得很慢，但均摊．．复杂度依然是O(nlogn)。例如NOI2006的生日快乐（happybirthday），SBT在最后一个点可以做到3s跑过，而MaShuo的Splay只能做到6s，我的Splay更是用了8s才跑过了最后一个点（全部在本机测试）。程序见happybirthday_winsty_sbt.dpr，happybirthday_MaShuo_Splay.dpr和happybirthday_sqybi_Splay.dpr。神奇的Splay(TheMagicalSplay)Aproductofsqybi3基本操作参见芜湖一中杨思雨的论文《伸展树的基本操作与应用》和马朔的《伸展树操作详解》。旋转无论是什么平衡二叉树，都会用到旋转操作。旋转操作可以使得某一个结点提升到他父亲的位置而不破坏平衡二叉树的性质。下面是一个很经典的旋转的图示：图1旋转操作其中我们将ZIG操作称为右旋，而ZAG操作称为左旋。另外为了描述方便，对于图中的ZIG操作，我们称作将．x．结点右旋．．．．（而不是某些论文里提到的将y结点右旋，读者可以很容易发现这两种描述是等价的）；同样对于图中的ZAG，我们称作将y结点左旋。为什么旋转操作不破坏二叉树的性质呢？下面我们来简单的以ZIG操作举例说明。我们用A，B，C表示A，B，C这三棵子树里所有值组成的集合。那么我们有：cybxaCcBbAa,,,而很容易发现，在ZIG操作之后，这种关系仍然满足。实际上，ZIG和ZAG的思想很简单。以ZIG为例，只是将x的右子树B先暂时拿开，然后将y接到x的右子树上，x接到原先y的位置上，再把B接到y的左子树上，ZIG操作就完成了。程序中实际的实现也是这样做的。0102030405060708091011121314151617PROCEDURELeftRotate(x)y←Father[x]RightSon[y]←LeftSon[x]IF(LeftSon[x]0)Father[LeftSon[x]]←yENDIFFather[x]←Father[y]IF(Father[y]0)IF(y=LeftSon[father[y]])LeftSon[father[y]]←xELSERightSon[father[y]]←xENDIFENDIFLeftSon[x]←yFather[y]←xUpdate(x)神奇的Splay(TheMagicalSplay)Aproductofsqybi41819Update(y)ENDPROCEDURE读者可以自行完成RightRotate(x)操作，而我们可以发现这两种操作很接近。所以，实际实现中为了简便，我们用Rotate(w,x)代替以上两种旋转操作——w=0为左旋，w=1为右旋。同时son[0,x]替代LeftSon[x]，son[1,x]替代RightSon[x]。具体程序见superbt.dpr。程序里的Update(x)操作表示将x结点的size域更新（size[x]表示x这棵子树的结点个数，包括x结点，在后面的查找第k小的操作中会用到）。更新时只需要size[x]←size[LeftSon[x]]+size[RightSon[x]]。为了避免LeftSon[x]或RightSon[x]等于0，我们可以让size[0]←0。伸展操作伸展操作是Splay的精髓，也是Splay维护平衡的关键（如果没有Splay操作，伸展树就无法保证O(nlogn)的均摊复杂度）。伸展操作仅仅用到了两种Rotate的简单组合——组合出的四种新操作称作ZIG-ZAG，ZAG-ZIG，ZIG-ZIG与ZAG-ZAG，加上原先的ZIG和ZAG，总共六种操作，对应三种不同情况。考虑需要将x结点伸展到根的操作。第一种情况：如果x结点的父亲y已经是根结点，我们只需要简单的对它做ZIG或ZAG的操作，它就会被伸展到根，如图1所示。第二种情况：如果x结点的父亲y不是根结点，设y结点的父亲为z。若y是z的左孩子，且x是y的左孩子，则我们进行ZIG-ZIG操作；若y是z的右孩子，且x是y的右孩子，则我们进行ZAG-ZAG操作。以ZIG-ZIG为例，我们需要做的只是将y结点先ZIG，再将x结点ZIG。很显然这样x结点就会替代原先z结点的位置。实际上，ZIG-ZIG操作之后结点的位置变化如图2：图2ZIG-ZIG操作ZAG-ZAG操作类似。第三种情况：如果x结点的父亲y不是根结点，设y结点的父亲为z。若y是z的左孩子，且x是y的右孩子，则我们进行ZAG-ZIG操作；若y是z的右孩子，且x是y的左孩子，则我们进行ZIG-ZAG操作。对于ZIG-ZAG操作，和ZIG-ZIG有所不同——它需要先把x结点右旋，再把y结点左旋。旋转后结点变化如图3：图3ZIG-ZAG操作神奇的Splay(TheMagicalSplay)Aproductofsqybi5或许这些ZIG和ZAG排列组合出的名字能让你们头昏脑胀，没关系，这是正常的生理反应^_^。你只需要记住以下几点，上面的就都可以忽略了（那我写那些干什么=.=!）。如果当前结点是根节点的孩子，直接旋转一次即可。如果当前结点，当前结点的父亲结点，当前结点的父亲结点的父亲结点三点成一直线，先旋转当前结点的父亲结点，再旋转当前结点。如果当前结点，当前结点的父亲结点，当前结点的父亲结点的父亲结点三点成一折线，先旋转当前结点，再旋转当前结点的父亲结点。可以根据图2和图3中的例子自己在草稿纸上模拟一下，印象会更深刻~010203040506070809101112131415161718192021222324252627282930313233PROCEDURESplay(x)y←0WHILE(father[x]y)IF(Father[Father[x]]=y)IF(x=LeftSon[Father[x]])RightRotate(x)ELSELeftRotate(x)ENDIFELSEIF(Father[x]=LeftSon[Father[Father[x]]])IF(x=LeftSon[Father[x]])RightRotate(Father[x])RightRotate(x)ELSELeftRotate(x)RightRotate(x)ENDIFELSEIF(x=RightSon[Father[x]])LeftRotate(Father[x])RightRotate(x)ELSERightRotate(x)LeftRotate(x)ENDIFENDIFENDIFENDWHILEIF(y=0)root←xENDIFENDPROCEDURE神奇的Splay(TheMagicalSplay)Aproductofsqybi6注意到程序中使用到变量y，且y被赋值0。y的含义是，使x在Splay操作结束后作为y的孩子。上面介绍的Splay需要将x伸展到根结点，伸展后x的父亲为0（即没有父亲），所以y=0。实际上我们可以使y的值为x的任意一个祖先（Splay函数定义为Splay(x,y)），这样Splay操作就更加灵活，可以将x伸展到任何．．我们想要的位置（想想为什么可以做到？）。后面的程序中会用到这种灵活的伸展。神奇的Splay(TheMagicalSplay)Aproductofsqybi7进阶操作接下来文章会介绍其它平衡二叉树也都会用到的一些经典操作：插入一个数，删除某个特定值，查找某个值在数据结构中的排名（即查询它是第几小的数），查找某个排名的数是多少。对于后两种操作，我们需要维护一个size域。而size域也可以用于维护重复元素。插入操作对于Splay来说，插入操作和其它平衡二叉树没有什么太大的区别，唯一的不同就在于插入操作之后需要将刚插入的结点伸展到根。这看起来没有什么必要，但详细的论证表示伸展操作可以降低树的高度，从而保证O(nlogn)的均摊复杂度。具体的证明见杨思雨的论文《伸展树的基本操作与应用》。这里以没有重复元素的插入为例。插入时，首先从根节点开始，每次判断需要插入的数据的序号与当前结点的序号。如果需要插入的数据较小，则插入到右子树，否则插入到左子树中。如果需要插入的位置没有结点，那么中止循环，并在此位置插入一个结点。插入结点之后，不要忘记．．．．把这个结点伸展到根（有兴趣的话可以尝试一下对任意一个子程序省略这句Splay操作，你会惊奇的发现Splay的速度慢了10倍甚至更多，如果不是随机数据的话；当然对Insert操作省略这句话会使Splay变得更慢）。010203040506070809101112131415161718192021222324252627PROCEDUREInsert(v