[原创]伸展树(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)的了

单旋: 左旋(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树的树根放到呢个腾出的空节点位置就行了，

1

总结

SPLAY操作非常灵活多变,一定要理解SPLAY然后去使用,不要只会套板子就结束了,

有几点特别要注意的地方
1.插入/删除节点的时候注意父节点要修改
2.sz[]维护不要出错
3. …

附上整体代码-md贴上来太卡了,去题解里看吧
注：这两个板子没有用双旋，用的单旋。。

维护序列的
维护一堆数的