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];}

核心操作

不太容易理解,非常重要

旋转操作

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

旋转分为左旋和右旋,两者对称。先来看右旋:
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=++tot;//新建结点
if(p)ch[p][val[p]<key]=u;
ch[u][0]=ch[u][1]=0,pa[u]=p,val[u]=key,sz[u]=cnt[u]=1;//更新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];//左子树
elsse 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/