Splay 初步

2019.6.19 编入精选文章。

前言

平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了。在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。

——维基百科

常见平衡树

实现平衡树的手段很多,在这里我们列举出 OI 中常见的一些平衡树:

  1. Treap
  2. FHQ Treap
  3. Splay
  4. 替罪羊树
  5. 重量平衡树

今天我们着重介绍 Splay。

伸展树 ·Splay

伸展树的自我平衡使其拥有良好的性能,因为频繁访问的结点会被移动到更靠近根结点,进而获得更快的访问速度。唯一的不足,平衡性不稳定,均摊复杂度 ,最坏复杂度 .

先看一下维护的信息:

根结点 结点总数 父结点 左右子结点 结点键值 键值出现次数 子树大小

平衡树需要对一颗树维护以下操作:

函数 意义
get(u) 判断 u 是父结点的左儿子还是右儿子
pushup(u) 在改变 u 的位置前,更新 sz[u]
rotate(u) 把 u 旋转到它的父结点
splay(u,v) 把 u 旋转到 v 的儿子,v=0 时表示旋转到根结点
find(key) 查找键值为 key 的结点并 splay 到根结点
insert(key) 插入键值 key 并 splay 到根结点
rank(key) 查询键值排名
kth(k) 查询第 k 小的数
pre(key) 查询键值为 key 的结点的前驱
suc(key) 查询键值为 key 的结点的后继
del(key) 删除一次键值 key

接下来我们逐一讲解

结构声明

首先要明确的是,splay 中的各结点键值是互不相同的,键值的中序遍历序列是严格单调递增

其次,我们事先会在 splay 中插入两个键值分别为 的结点,以方便边界的判断。

在 splay 中一定要分清结点编号和键值的区别

基础操作

很好理解,也很重要。这些操作是可以不写的。但把他们封成函数可以增强可读性。

判断身份

显然是一个布尔函数

bool get(int u){return u==ch[pa[u]][1];}
// 为左儿子返回 0,为右儿子返回 1

更新子树大小

用子结点的大小更新

void pushup(int u){sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+cnt[u];}

新建结点

新建一个键值为 key 的结点。这里的新建的结点不考虑指针,指针在外面赋值。

int new_node(int key){
    ++tot, ch[tot][0]=ch[tot][1]=0,val[tot]=key,sz[tot]=cnt[tot]=1;
    return tot;
}

核心操作

不太容易理解,非常重要

旋转操作

所有的平衡树要维护平衡,都是依靠旋转实现的。不同的平衡树会根据不同的情况,不同的条件旋转,但本质都是使深度较大的子树深度变小,达到趋近平衡的目的。

旋转分为左旋和右旋,两者对称。先来看右旋:(谅解一下灵魂的作图

tree_rotate.png

图中略去了 CDE 的子结点和 A 的父结点,可将其理解为,把 B 扯到 A 的位置,A 下坠成为 B 的右子结点,然后将 B 原本的右子结点改为 A 的左子结点。

旋转以后并没有改变二叉搜索树的性质,这里重点说明一下 E 的变化。E 本来比 B 大,比 A 小;旋转以后,E 仍比 A 小,仍比 B 大。

经过右旋,以 B 为根的子树深度减少 1,以 A 为根的子树深度增加 1。利用这样此消彼长的操作,就使得二叉树趋于平衡。

将右旋反过来,就是左旋。

就根据上面的图,我们把左旋和右旋合在一起,步骤如下:

  1. 获取三个值:当前结点的身份 ,父结点的编号 ,在 异侧子结点的编号 .
  2. 变成 的子结点,把 变成 的结点,新的 的身份分别为 .
  3. 更新各自的子树大小。
void rotate(int u){
    int p=pa[u],pp=pa[p],k=get(u);
    ch[pp][get(p)]=u,pa[u]=pp;// 建立 u 和 u 的爷爷结点的联系
    ch[p][k]=ch[u][k^1],pa[ch[u][k^1]]=p;// 建立 ch[u][k^1] 和 pa[u] 的联系
    ch[u][k^1]=p,pa[p]=u;// 建立 u 和 pa[u] 的联系
    pushup(p),pushup(u);// 先更新 p 再更新 u
}

伸展操作

Splay 利用伸展操作趋近平衡。具体描述为,将当前访问过的结点旋转至根结点的位置。

这样旋转的好处在于,经常访问的结点访问速度将速度很快(因为就在根结点附近),而且在旋转的过程中,整棵树也会逐渐平衡。

设访问过的结点为 x,其父结点为 p,伸展操作将循环考虑以下三种情况,直到 x 成为根结点:

  • p 是根结点 -Case1
  • p 不是根结点时,p,x 为同侧结点 -Case2
  • p 不是根结点时,p,x 为异侧结点 -Case3

这里只讲解左右结点中的情况,另一种是对称的

Case1

p 为根结点,直接旋转一次即可,然后伸展操作结束。

Zig.png

Case2

p,x 为同侧结点,则按顺序做两次同向旋转即可:

Zig-zig.png

Case3

p,x 为异侧结点,则做两次异向旋转即可:

Zig-zag.png

void splay(int u,int v){// 把 u 旋转到 v 的儿子
    while(pa[u]!=v){
        int p=pa[u];
        if(pa[p]!=v)rotate(get(u)==get(p)?p:u);// 同侧就旋转 p,异侧就旋转 u
        rotate(u);// 旋转 u
    }
    if(!v)rt=u;// 标记根结点
}

查询键值

即二叉查找树的查询,左右判断查找键值是否存在

不过 splay 的查询函数不会给出返回值,而是直接把找到的键值对应的结点 splay 到根结点上

如何没有找到,就会把离这个键值最近的结点 splay 到根结点上

void find(int key){
    if(!rt)return;// 如果树是空的就返回
    int u=rt;
    while(val[u]!=key&&ch[u][val[u]<key])u=ch[u][val[u]<key];
    splay(u,0);// 伸展到根结点
}

插入键值

即二叉查找树的插入,如果有键值就增加 cnt,否则新建结点

当然,把插入的键值对应的结点 splay 到根结点

在这里我们不套用查询键值的函数,不然不方便新建结点

void insert(int key){
    int u=rt,p=0;//p 是 u 的父结点
    while(val[u]!=key&&u)p=u,u=ch[u][val[u]<key];//while 的条件不同于 find(key)
    if(u)++cnt[u];// 找到键值
    else u=new_node(key), p?ch[p][val[p]<key]=u:0,pa[u]=p;// 更新 u 的 5 项信息
    splay(u,0);// 伸展到根结点
}

这里解释一下末尾的 splay 操作的必要性:当在空的树中插入结点的时候就尤其重要,因为 splay 会根据伸展完之后结点的位置来更新根结点 的值,那么在插入第一个结点的时候就会顺便记录它为根结点。

附加操作

建立在核心操作之上,比较简单

查询键值排名

这里的排名中,重复的键值算一次。所以把键值旋转到根结点,获取左子树的大小 +1 即可

注意我们一开始是插入了 这个结点的,所以代码实现上是不用 +1 的

int rank(int key){
    find(key);
    return sz[ch[rt][0]];
}

第 k 小数

这里指包括重复键值的情况,过程都差不多,从根结点往下找。每次与左子树和当前结点的 cnt 的和比较,该左就左该右就右。返回第 k 小数的键值(其实结点编号也行,看需求)

int kth(int k){
    ++k;// 因为有 -INF 的结点
    int u=rt;
    while(1){
        if(sz[ch[u][0]]+cnt[u]<k)k-=sz[ch[u][0]]+cnt[u],u=ch[u][1];// 右子树
        else if(k<=sz[ch[u][0]])u=ch[u][0];// 左子树
        else return val[u];
    }
}

查询前驱

即查询键值的前驱(严格小于),返回结点的编号

int pre(int key){
    find(key);
    if(val[rt]<key)return rt;
    int u=ch[u][0];// 在左子树中找最大值
    while(ch[u][1])u=ch[u][1];
    return u;
}

查询后继

同理

int suc(int key){
    find(key);
    if(val[rt]>key)return rt;
    int u=ch[u][1];// 在右子树中找最小值
    while(ch[u][0])u=ch[u][0];
    return u;
}

删除操作

我们把这家伙专门列一个大点。其实就之前的操作而言,我们的 splay 都是伸展到根结点的,那么 参数到底有什么用?没错,就是在这里用的。

在删除键值的时候,如果 cnt 大于 1 那就直接 cnt-1,但是遇到 cnt=1 的时候,就要删除结点。普通的二叉查找树需要递归删除后继结点,比较麻烦。而在 splay 上我们结合查询前驱、后继的操作,就可以实现直接删除啦

void del(int key){
    int pr=pre(key),su=suc(key);// 找到前驱后继
    splay(pr,0),splay(su,pr);// 把前驱伸展到根结点,把后继伸展到前驱的子结点
    int u=ch[su][0];// 这时的 key 一定是该后继的左子结点,而且这个结点 u 没有子结点
    if(cnt[u]>1)--cnt(u),splay(u,0);// 老老实实伸展到根结点
    else ch[su][0]=0,splay(su,0);// 删除结点 u,splay 操作用来更新 sz
}

小结

完整代码就不贴啦,就是全部拼起来加上变量的定义啦

全部拼起来就可以过 Luogu 模板啦

所以 Splay 其实也不难,只是函数比较多,但每个函数的内容都不多

理解了以后还是很简单的

参考文献

丁思源 . 「算法笔记」Splay . https://hydingsy.github.io/articles/algorithm-Splay/


  转载请注明: Sshwy's Blog Splay 初步

 上一篇
并查集 ·Disjoint 并查集 ·Disjoint
摘要 并查集(Union-Find Set)用于处理元素间可传递的关系,通常以集合的方式呈现。 并查集本身又是一种树结构(由若干棵树组成的不相交森林),用树的根结点(代表元)来区分不同的集合。 并查集并查集支持以下基本操作: Get(
2018.12.19
下一篇 
线段树初步 线段树初步
线段树基础线段树,是利用一个区间建立一个完全二叉树,来快速实现区间修改、查询操作。 例如,要求对序列 A{1,3,4,2,5,3,7,8} 进行如下两种操作: add(l,r,v): 把 [l,r] 的元素都增加 v sum(l,r):
2018.12.19
  目录