[原创]伸展树(SPLAY)个人总结+模板 [平衡树]【数据结构】【模板】
2017-06-21 14:52:43 Tabris_ 阅读数:1804
博客爬取于2020-06-14 22:39:10
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/73549164
前言 最近3个月内,无论是现场赛还线上赛中SPLAY出现的概率大的惊人啊啊啊!!! 然而不会的我就GG了,同时发现大家都会SPLAY,,,,然后就学习了一波。
开始怎么学都学不懂,直到看到一句话
想学好splay,只要把伸展和旋转操作弄懂,就好了. (而这两个想要学会就是需要自己画图自己理解了)
于是茅塞顿开,有了本文, 本文重点是SPLAY维护序列的操作,而非SPLAY本身,这部分会说的比较粗略,二叉树的部分更不会有说明,
菜(sha3)逼我也只是初学,如果有描述不当甚至错误的地方,欢迎指正
定义 伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。
同其他平衡树一样,都是在二叉排序树的基础上进行操作的,但不同于AVL需要记录平衡信息,也没有红黑树实现上的难度.是一种综合考量下很适合应用于信息学竞赛的平衡树.
对于一个基本的SPLAY 我这样定义
1 2 3 4 5 6 7 int ch[N][2]; //ch[][0] 表示左儿子 ch[][1] 表示右儿子 int f[N]; //节点的父亲节点 int sz[N]; //当前节点给所在的子树的节点个数 int val[N]; //当前节点表示的值 int cnt[N]; //当前节点所表示的值的个数 int root; //记录根节点的 int tot; //计算树中节点个数
构建的过程也就和普通二叉树一样了,递归下去即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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 ( log n ) O(\log n) O ( log n ) 的了
单旋: 左旋(zag)&右旋(zig)
双旋: 通过树的旋转来自我调整来保持平衡,就是基于这两个操作左旋(zag)&右旋(zig) ,还有其延伸出的操作
下面来实现下旋转操作
总之就是对每次旋转节点间关系信息发生改变的位置调整好就行 需要点耐心,不要调错
1 2 3 4 5 6 7 8 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); }
伸展 经过多次旋转,将节点位置坐出调整的操作就是伸展了
来举个栗子,对于一个退化为单链的树进行旋转
双旋的写法,比较稳定
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void splay(int x,int goal){//将x旋转到goal的下面 while(f[x] != goal){ if(f[f[x]] == goal) rotate(x , ch[f[x]][0] == x); else { int y=f[x],z=f[y]; int K = (ch[z][0]==y); if(ch[y][K] == x) rotate(x,!K),rotate(x,K); else rotate(y,K),rotate(x,K); } } pushup(x); if(goal==0) root=x; }
而我发现zig-zag这种两个旋转合在一起的操作,其实是两遍单旋,所以只要每次都向上单旋就行了,
1 2 3 4 5 6 单旋容易被卡 不懂 百度伸展树单双旋的比较 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 】做补充,如果不完全,后期会补上
一些基本操作 查找 查找部分和普通的二叉查找树一模一样,只要遍历下去即可
1 2 3 4 5 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所在的节点,然后在左右子树,找最右左的节点即可
1 2 3 4 5 //以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[],很容易得到每个节点是第几个,不断的在树上二分就行,
1 2 3 4 5 6 //以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++就行了, 假如要插入的点在x 那么让x-1做为树根,x+1伸展到根节点下面,那么x+1的左儿子就是空出来的 加个值就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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); }
删除 和删除一样,就是反过来了而已, 首先这个值如果不存在,那就直接return即可 如果这个值大于1,那就cnt–即可 如果这个值所在的节点的儿子节点有空的,那么就把需要提上去的儿子节点提上去即可 如果这个值所在的节点的儿子节点都存在,那么就把这个节点的前驱提到根节点,后继提到根节点的下面,那样的话删除ch[ch[root][1]][0]就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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),s=sufc(x); splay(p,0);splay(s,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这两个节点
1 2 3 4 5 6 //区间加 void add(int l,int r,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); }
区间翻转 同样在一个二叉树中 翻转也就是让每个节点的两个儿子交换一下顺序就好了, 打个标记 就行了,
1 2 3 4 5 6 //区间翻转 void reversal(int l,int r){ int x=kth(root,l-1),y=kth(root,r+1); splay(x,0);splay(y,x); update_rev(ch[y][0]); }
区间交换 所以我们可以将后一个区间处理到一个子树上,然后放到l−1,l 这两个节点之间,就好了,先减掉,然后在加上去就好了
1 2 3 4 5 6 7 8 9 10 //区间交换 void exchange(int l1,int r1,int l2,int r2){ int x=kth(root,l2-1),y=kth(root,r2+1); splay(x,0),splay(y,x); int tmp_right = ch[y][0]; ch[y][0]=0; x=kth(root,l1-1),y=kth(root,l1); splay(x,0),splay(y,x); ch[y][0] = tmp_right; f[tmp_right]=y; }
合并 合并是指两颗SPLAY进行合并, 要求这两颗树没有交错的部分,(可能没有这个限制,但是我不会,)
首先处理好一个树A加入到B中,那么在B中腾出一个空节点来代替A树需要的段,然后把A树的树根放到呢个腾出的空节点位置就行了,
总结 SPLAY操作非常灵活多变,一定要理解SPLAY然后去使用,不要只会套板子就结束了,
有几点特别要注意的地方 1.插入/删除节点的时候注意父节点要修改2.sz []维护不要出错 3. …
附上整体代码-md贴上来太卡了,去题解里看吧注:这两个板子没有用双旋,用的单旋。。
维护序列的 维护一堆数的