前言
最近3个月内,无论是现场赛还线上赛中SPLAY出现的概率大的惊人啊啊啊!!!
然而不会的我就GG了,同时发现大家都会SPLAY,,,,然后就学习了一波。
开始怎么学都学不懂,直到看到一句话
想学好splay,只要把伸展和旋转操作弄懂,就好了.
@H_403_13@
(而这两个想要学会就是需要自己画图自己理解了)于是茅塞顿开,有了本文,
本文重点是SPLAY维护序列的操作,而非SPLAY本身,这部分会说的比较粗略,二叉树的部分更不会有说明,菜(sha3)逼我也只是初学,如果有描述不当甚至错误的地方,欢迎指正
定义
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。
同其他平衡树一样,都是在二叉排序树的基础上进行操作的,但不同于AVL需要记录平衡信息,也没有红黑树实现上的难度.是一种综合考量下很适合应用于信息学竞赛的平衡树.
对于一个基本的SPLAY 我这样定义
int ch[N][2]; //ch[][0] 表示左儿子 ch[][1] 表示右儿子 int f[N]; //节点的父亲节点 int sz[N]; //当前节点给所在的子树的节点个数 int val[N]; //当前节点表示的值 int cnt[N]; //当前节点所表示的值的个数 int root; //记录根节点的 int tot; //计算树中节点个数
构建的过程也就和普通二叉树一样了,递归下去即可
void newnode(int rt,int v,int fa){ f[rt]=fa; val[rt]=v;sz[rt]=1; ch[rt][0]=ch[rt][1]=0; } void delnode(int rt){ f[rt]=sz[rt]=val[rt]=0; ch[rt][0]=ch[rt][1]=0; } void build(int &rt,int l,int r,int fa){ if(l>r) return ; int m = r+l >> 1; rt=m; newnode(rt,val[rt],fa);cnt[rt]=1; build(ch[rt][0],l,m-1,rt); build(ch[rt][1],m+1,r,rt); pushup(rt); } void init(int n){ root=0; f[0]=sz[0]=ch[0][0]=ch[0][1]=rev[0]=0; build(root,1,n,0); pushup(root); }
旋转
对于一颗二叉排序树,根据序列的信息很容易找到某一个值,只要不断的向下搜索下去即可,复杂度是O(树高),
但是二叉树最坏的情况下是会退化成一个单链的,这是后查找的复杂度就是O(n)了,非常不可取而在SPLAY中控制树保持平衡需要的就是旋转操作,是树保持平衡,这样复杂度就变成了均摊
O(logn) 的了单旋: 左旋(zag)&右旋(zig)
双旋:
通过树的旋转来自我调整来保持平衡,就是基于这两个操作左旋(zag)&右旋(zig),还有其延伸出的操作
下面来实现下旋转操作
总之就是对每次旋转节点间关系信息发生改变的位置调整好就行
@H_403_13@
需要点耐心,不要调错void rotate(int x,int k){ // k = 0 左旋, k = 1 右旋 int y=f[x];int z=f[y]; pushdown(y),pushdown(x); ch[y][!k]=ch[x][k];if(ch[x][k])f[ch[x][k]]=y; f[x]=z;if(z)ch[z][ch[z][1]==y]=x; f[y]=x;ch[x][k]=y; pushup(y),pushup(x); }
伸展
经过多次旋转,将节点位置坐出调整的操作就是伸展了
来举个栗子,对于一个退化为单链的树进行旋转
一个比较普通的写法是分成6种来写 代码比较长
inline void splay(int x){ //将x调整为树根 int y; while(father[x]){ y=father[x]; if(!father[y]){ if(x==son[y][1]) Rotate(x,2); else Rotate(x,1); } else{ if(y==son[father[y]][1]){ if(x==son[y][1]) Rotate(y,2),Rotate(x,2); else Rotate(x,1),2); } else { if(x==son[y][2]) Rotate(y,1); else Rotate(x,1); } } } root = x; return ; }
而我发现zig-zag这种两个旋转合在一起的操作,其实是两遍单旋,所以只要每次都向上单旋就行了,
void splay(int x,int goal){ //将x调整为goal的儿子,(如果要调整到根goal就是0) for(int y=f[x];f[x]!=goal;y=f[x]) rotate(x,(ch[y][0]==x)); //(ch[y][0]==x)计算是左旋还是右旋,看x是左右儿子哪一个区分开了 if(goal==0) root=x; }
各种操作
对于SPALY能够做到的操作以【BZOJ3224 普通平衡树】为引,以 【BZOJ 1895 & POJ 3580 supermemo 】做补充,如果不完全,后期会补上
@H_403_13@一些基本操作
查找
查找部分和普通的二叉查找树一模一样,只要遍历下去即可
@H_403_13@int search(int rt,int x){ if(ch[rt][0]&&val[rt]>x) return search(ch[rt][0],x); else if(ch[rt][1]&&val[rt]<x)return search(ch[rt][1],x); else return rt; }
极值 & 前驱,后继
前驱:小于x的最大的数
后继:大于x的最小的数先找到x所在的节点,然后在左右子树,找最右左的节点即可
@H_403_13@//以x为根的子树 的极值点 0 极小 1 极大 int extreme(int x,int k){ while(ch[x][k])x=ch[x][k];splay(x,0); return x; }
第K个数
第k个数,通过记录的sz[],很容易得到每个节点是第几个,不断的在树上二分就行,
//以x为根的子树 第k个数的位置 int kth(int x,int k){ if(sz[ch[x][0]]+1==k&&k<=sz[ch[x][0]]+cnt[x]) return x; else if(sz[ch[x][0]]>=k) return kth(ch[x][0],k); else return kth(ch[x][1],k-sz[ch[x][0]]-cnt[x]); }
一些正经的操作
插入
假如要插入的点已经存在了,那么cnt++就行了,
@H_403_13@
假如要插入的点在x
那么让x-1做为树根,x+1伸展到根节点下面,那么x+1的左儿子就是空出来的 加个值就好了void _insert(int x){ int y=search(root,x),k=-1; if(val[y]==x){ cnt[y]++; sz[y]++; for(int yy=y;yy;yy=f[yy]) pushup(yy); } else { int p=prec(x),s=sufc(x); splay(p,0);splay(s,p); newnode(++tot,x,ch[root][1]); ch[ch[root][1]][0]=tot; for(int z=ch[root][1];z;z=f[z])pushup(z); } if(k==-1) splay(y,0);else splay(tot,0); }
删除
和删除一样,就是反过来了而已,
@H_403_13@
首先这个值如果不存在,那就直接return即可
如果这个值大于1,那就cnt–即可
如果这个值所在的节点的儿子节点有空的,那么就把需要提上去的儿子节点提上去即可
如果这个值所在的节点的儿子节点都存在,那么就把这个节点的前驱提到根节点,后继提到根节点的下面,那样的话删除ch[ch[root][1]][0]就行了void _delete(int x){ int y=search(root,x); if(val[y]!=x) return; if(cnt[y]>1){ cnt[y]--; sz[y]--; for(int yy=y;yy;yy=f[yy]) pushup(yy); } else if(ch[y][0]==0||ch[y][1]==0){ int z=f[y]; ch[z][ch[z][1]==y]=ch[y][ch[y][0]==0]; f[ch[y][ch[y][0]==0]]=z;delnode(y); for(int yy=z;yy;yy=f[yy]) pushup(yy); } else { int p=prec(x),p); ch[ch[root][1]][0]=0; delnode(ch[ch[root][1]][0]); for(int yy=s;yy;yy=f[yy]) pushup(yy); } }
区间加
区间操作
对于区间[l,r]
那么让l-1做为树根,r+1伸展到根节点下面,那么r+1的左儿子就是这个区间
打上lazy_tag就行了但为了更好的处理[1,n]这个区间 加上个0和n+1这两个节点
@H_403_13@//区间加 void add(int l,int v){ int x=kth(root,l-1),y=kth(root,r+1); splay(x,0);splay(y,x); update_add(ch[y][0],v); }
区间翻转
同样在一个二叉树中 翻转也就是让每个节点的两个儿子交换一下顺序就好了,打个标记 就行了,
@H_403_13@//区间翻转 void reversal(int l,int r){ int x=kth(root,x); update_rev(ch[y][0]); }
区间交换
所以我们可以将后一个区间处理到一个子树上,然后放到l−1,l 这两个节点之间,就好了,先减掉,然后在加上去就好了
@H_403_13@//区间交换 void exchange(int l1,int r1,int l2,int r2){ int x=kth(root,l2-1),r2+1); splay(x,0),splay(y,x); int tmp_right = ch[y][0]; ch[y][0]=0; x=kth(root,l1-1),l1); splay(x,x); ch[y][0] = tmp_right; f[tmp_right]=y; }
合并
合并是指两颗SPLAY进行合并,
要求这两颗树没有交错的部分,(可能没有这个限制,但是我不会,)首先处理好一个树A加入到B中,那么在B中腾出一个空节点来代替A树需要的段,然后把A树的树根放到呢个腾出的空节点位置就行了,
总结
SPLAY操作非常灵活多变,一定要理解SPLAY然后去使用,不要只会套板子就结束了,
有几点特别要注意的地方
1.插入/删除节点的时候注意父节点要修改
2.sz[]维护不要出错
3. ……——————————————————————————-
附上整体代码-md贴上来太卡了,去题解里看吧