[2018.10.24]Splay伸展树(数据结构)

今天学的第二种树了。(下午学的主席树->[主席树](https://www.luogu.org/blog/xryjr233/post-20181024-zhu-xi-shu-shuo-ju-jie-gou-post)) 从前，有一种东西叫做二叉搜索树(Binary Search Tree)，它可以支持**期望**单次$O(logn)$的查找、插入、删除等操作。 但是，期望。。。这个词在OI里是要命的。你知道世界上所有的出题人都知道怎么卡掉它。 所以它就衍生出各种优化(AVL树、Treap、Splay等)。其中，我们神奇的Tarjan奆佬发明了Splay(这位奆佬还发明了一堆图论算法和数据结构，证明了一堆结论)。 要想了解Splay在干什么，我们需要知道BST在做什么，为什么会被卡。 BST是一棵二叉树(废话)，它满足一个特殊的性质:任何一个节点的左子树的所有节点权值都小于这个节点，右子树的所有节点权值都小于这个节点。 当插入一个节点时，它可以根据这个性质确定这个节点应该在的位置。比如在插入顺序如下时，它的复杂度是很优秀的$O(logn)$：  但是，当插入顺序如下时，它的时间复杂度变为了$O(n)$：  所以，Splay(和它的兄弟姐妹们)就出现了。 为了维护树的平衡，Splay使用了splay操作，这也是它名字的由来。 Splay操作由若干次旋转(rotate)来实现。旋转操作的用意是：将一个节点旋转到它的父亲的位置上，并且不改变其大小关系。 一、旋转操作rotate(x) 意思是将**编号**为x的节点旋转到它的父亲的位置上。 假设x的父亲节点为y，祖父节点为z。x为y的a儿子(0左1右)，y为z的b儿子(0左1右)，$\bigoplus$为二进制的异或运算。 则操作如下: 1.z的b儿子变为x； 2.y的a儿子变为x的(a$\bigoplus$1)儿子； 3.x的(a$\bigoplus$1)儿子变为y。 code: ```cpp void Rotate(int x){//d为Splay的结构体数组，结构体中的c[0]为左儿子,c[1]为右儿子,f为父节点,val为点的权值。 int f=d[x].f;//f为x的父亲 int gf=d[f].f;//gf为x的祖父(不是女朋友) int ws=(d[f].c[1]==x),gws=(d[gf].c[1]==f);//ws为x是y的什么儿子,gws为y是z的什么儿子，仔细想想就能看懂了 d[gf].c[gws]=x; d[x].f=gf; d[f].c[ws]=d[x].c[ws^1]; d[d[x].c[ws^1]].f=f; d[x].c[ws^1]=f; d[f].f=x;//记得在更新子节点后更新父节点 } ``` 二、伸展操作splay(x,fa) 意思是将**编号**为x的节点伸展为**编号**为fa的节点的儿子。 假设x的父亲节点为y，祖父节点为z，x为y的a儿子(0左1右)，y为z的b儿子(0左1右)。具体操作如下： 1.假如y是fa，结束； 2.假如z是fa，则对x进行旋转； 3.假如a$\ne$b，则连续对x进行两次旋转，并再次开始该操作； 4.假如a$=$b，则先对y进行一次旋转，再对x进行一次旋转，并再次开始该操作。 code: ```cpp void Splay(int x,int fa){//将x伸展到fa的儿子,fa=0则旋转到根 while(d[x].f!=fa){//重复直到fa为x的父亲 if(d[d[x].f].f==fa){//单旋 Rotate(x); }else{ int f=d[x].f; int gf=d[f].f; int ws=(d[f].c[1]==x),gws=(d[gf].c[1]==f); if(ws==gws){//a等于b Rotate(f); }else{//a不等于b Rotate(x); } Rotate(x);//两者的共同操作 } } if(!fa){//如果旋转到根，更新根 rt=x; } } ``` 三、查找操作find(x) 意思是寻找**权值**为x的节点并旋转到根，方便之后的操作。 根据BST的性质直接向下寻找，找到权值等于x的点时或不能再向下时停止查找，将当前节点伸展到根。 code: ```cpp void Find(int x){//查找权值为x的节点 int nd=rt;//开始为根 if(!nd){//空树 return; } while(d[nd].val!=x){//直到找到x if(d[nd].val>x){ if(!d[nd].c[0]){//不能向下了 break; } nd=d[nd].c[0];//跳到下一节点 }else{ if(!d[nd].c[1]){//不能向下了 break; } nd=d[nd].c[1];//跳到下一节点 } } Splay(nd,0);//伸展到根 } ``` 四、插入操作insert(x) 意思是往Splay里插入一个**权值**为x的节点。 类似查找操作向下寻找，找到时退出或者更新数量(视题目而定)，如果走到空节点就在此新建一个节点。 另外，为了维护平衡，新建节点后将它伸展到根。 code: ```cpp void Insert(int x){//插入权值为x的节点 int nd; if(!rt){//空树，直接作为根 rt=++cnt; d[rt].f=0; d[rt].c[0]=0; d[rt].c[1]=0; d[rt].val=x; nd=cnt; }else{ nd=rt;//从根开始 while(d[nd].val!=x){//查找x if(d[nd].val>x){ if(!d[nd].c[0]){//找不到，新建节点 d[nd].c[0]=++cnt; break; } nd=d[nd].c[0]; }else{ if(!d[nd].c[1]){//找不到，新建节点 d[nd].c[1]=++cnt; break; } nd=d[nd].c[1]; } } if(d[nd].val!=x){//如果需要新建节点 d[cnt].f=nd;//初始化节点信息 d[cnt].c[0]=0; d[cnt].c[1]=0; d[cnt].val=x; nd=cnt; } } Splay(nd,0);//伸展到根以维护平衡 } ``` 五、前驱/后继操作last(x)/next(x) 意思是求Splay中**权值**小于/大于x的最大/最小的节点。 将**权值**为x的节点伸展到根(如果存在的话)，则前驱为左子树(小于x)中最大的节点，一直跳右儿子即可。或者伸展后根的权值小于x，则根就是前驱。 后继为右子树(大于x)中最小的节点，一直跳左儿子即可。或者伸展后根的权值大于x，则根就是后继。 前驱后继有可能不存在。 code: ```cpp int Next(int x,int op){//op=0求x的前驱,op=1求后继 Find(x); if(op==0&&d[rt].val<x){//根就是前驱 return rt; } if(op==1&&d[rt].val>x){//根就是后继 return rt; } int nd=d[rt].c[op];//跳到左/右子树 if(!nd){//不存在 return -1; } while(d[nd].c[op^1]){//一直跳右/左儿子 nd=d[nd].c[op^1]; } return nd; } ``` 六、删除操作delete(x) 意思是删除**权值**为x的节点(有时是出现次数-1,视具体题目而定)。 显然大于x的前驱小于x的后继的数是x。 反应到Splay里，将前驱节点伸展到根，将后继节点伸展到根(前驱节点)的右儿子，后继节点的左儿子就是权值为x的节点(如果存在的话)。 code: ```cpp void Delete(int x){//删除权值为x的节点 int lst=Next(x,0);//前驱 int nxt=Next(x,1);//后继 Splay(lst,0);//前驱伸展到根 Splay(nxt,lst);//后继伸展为前驱的右儿子 d[nxt].c[0]=0;//删除 } ``` 还有一些合并、拆分什么的到时候再说吧。。。