文艺平衡树 Splay,也叫伸展树、分裂树,是一种二叉排序树,它能快速完成插入、查找和删除操作。它是由丹尼尔·斯立特 Daniel Sleator 和 罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明的。
$\text{Splay}$ 是一种强大的数据结构。
简介
$\text{Splay}$ 的本质是一颗进化的二叉查找树。
但它与普通的二叉查找树相比,难度较大,所以常常有人说“去掉 S 我就会”(play),“去掉 p 我就会”(Slay,一款游戏)或者去掉 Sp 我就会(lay,指 躺着
)。
下面介绍一下它的基本信息。
存储结构
用 root
表示整棵树的根节点编号。
编号为 $i$ 的节点存储:
- 父亲节点的编号,用
fa[i]
表示; - 左右儿子节点的编号(没有一般设置成 $0$),用
ch[i][0/1]
表示,ch[i][0]
表示左儿子,ch[i][1]
表示右儿子; - 当前节点的键值,用
val[i]
表示; - 以当前节点为根的子树大小,用
size[i]
表示; - 以当前节点内包含的元素个数,用
cnt[i]
表示。
基本操作
为了更加方便的操作
- $\operatorname{pushup}(x)$
将编号为 $x$ 的节点的信息(主要指size[x]
)更新。inline void pushup(reg int x){ size[x]=sizez[ch[x][0]]+sz[ch[x][1]]+cnt[x]; return; }
- $\operatorname{get}(x)$
查询当前节点是该节点父亲节点的左儿子还是右儿子,左儿子返回 $0$(false
),右儿子返回 $1$(true
)。inline bool get(reg int x){ return x==ch[fa[x]][1]; }
- $\operatorname{clear}(x)$
清空编号为 $x$ 的节点上储存的信息。inline void clear(reg int x){ fa[x]=ch[x][0]=ch[x][1]=0; val[x]=size[x]=cnt[x]=0; return; }
核心操作
- $\operatorname{rotate}(x)$
将 $x$ 旋转到原来父亲节点的位置上,同时不改变整棵树的中序遍历。
下面我们考虑两种情况:
$x$ 是父亲节点的左儿子。
$x$ 是父亲节点的右儿子。
于是可以写出代码。inline void rotate(reg int x){ reg int f=fa[x],ff=fa[f]; pushdown(x),pushdown(f); //这里的是魔改后的 Splay,所以与正常的有点不同 bool w=get(x); ch[f][w]=ch[x][w^1]; fa[ch[f][w]]=f; fa[f]=x; fa[x]=ff; ch[x][w^1]=f; if(ff) ch[ff][ch[ff][1]==f]=x; update(f); //这里的是魔改后的 Splay,所以与正常的有点不同 return; }
- $\operatorname{splay}(x,\text{goal})$
将 $x$ 转动到 $\text{goal}$ 的儿子位置($\text{goal}=0$ 表示把 $x$ 移到根节点的位置上)。inline void splay(reg int x,reg int goal){ for(reg int qwq;(qwq=fa[x])!=goal;rotate(x)) if(fa[qwq]!=goal) rotate(get(x)==get(qwq)?qwq:x); if(goal==0) root=x; return; }
- $\operatorname{insert}(x)$
插入键值为 $x$ 的节点。
插入操作是一个比较复杂的过程,具体步骤如下:- 如果树空了则直接插入根并退出。
- 如果当前节点的权值等于 $x$ 则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行 $\operatorname{splay}$ 操作。
- 否则按照二叉查找树的性质向下找,找到空节点就插入即可(当然别忘了 $\operatorname{splay}$ 操作哦)。
$\operatorname{find}(x)$
查找键值为 $x$ 的节点的编号。
二分查找。$\operatorname{kth}(x)$
求排名为 $x$ 的节点的权值。
查找过程有点像权值线段树。$\operatorname{pre}(x)$
查询 $x$ 的前驱。
前驱定义为小于 $x$ 的最大的数,那么查询前驱可以转化为:将 $x$ 插入(此时 $x$ 已经在根的位置了),前驱即为 $x$ 的左子树中最右边的节点,最后将 $x$ 删除即可。$\operatorname{nxt}(x)$
查询 $x$ 的后继。
后继定义为大于 $x$ 的最小的数,那么查询后继可以转化为:将 $x$ 插入(此时 $x$ 已经在根的位置了),后继即为 $x$ 的右子树中最左边的节点,最后将 $x$ 删除即可。$\operatorname{del}(x)$
删除 $x$。
把 $x$ 转到根然后像二叉查找树一样删除。
注意事项
- 查询前驱或后继时左右子树必须存在,不然有的写法容易死循环,所以推荐先插入正负无穷作为哨兵节点防止出错。
- 不要随意地魔改 $\text{Splay}$,它太神奇了,改之前记得画画图。
近期评论