一个月没写博客了,今后要更加努力啊
Splay Tree 是一种二叉排序树
通过不断旋转以维护单词操作复杂度为log(n)级别
在这里讲述的操作有:插入,删除,查询第k大,rank,前驱后继
旋转分三种情况
1.Zig
2.ZigZig
3.ZigZag
在这里不详细叙述旋转细节,而主要注重代码实现
int son[N][2]; //son[x][0]表示x的左儿子,son[x][1]表示x的右儿子
int f[N]; //f[x]表示x的父亲
int key[N]; //表示x的值
int cnt[N]; //表示x出现次数
int size[N]; //表示以x为根的子树大小
int root; //表示根结点
int sz; //表示整颗树的大小
clear(x)函数,用于删除x后的扫尾工作
void clear(int x){
son[x][1]=son[x][0]=cnt[x]=f[x]=key[x];
}
get(x)函数,判断x是父亲的左儿子还是右儿子,左返回0右返回1
int get(int x){
return son[f[x]][1]==x;
}
update(x)函数,用于维护信息的操作
在这里我只会维护子树大小。。
void update(int x){
if(x){
size[x]=cnt[x];
size[x]+=size[son[x][1]];
size[x]+=size[son[x][0]];
}
}
rotate(x) 重点的旋转操作
旋转前:
旋转后:
在这里要感谢EternalAlexander神犇制作的绘图工具 OI Painter
比较一下旋转前旋转后,不难发现③号节点被旋转到了原来它的父亲②号节点的位置,并且保持二叉排序树的性质
具有普遍性的讲就是将x结点旋转至x爷爷的儿子下,并且将原来x的父亲变为自己的儿子
步骤1
先找到x的父亲fa 与 x的爷爷(父亲的父亲) ff 并确定x是fa的左儿子还是右儿子
步骤2
将x移到fa的位置,根据大小关系可知
x如果是fa的左儿子,旋转以后fa是x的右儿子
x原来的右儿子变为fa的左儿子
x如果是fa的右儿子,旋转以后fa是x的左儿子
x原来的左儿子变为fa的右儿子
下文中的w表示x是父亲的左儿子还是右儿子,左儿子为0右儿子为1
inline void rotate(int x){
int fa=f[x],ff=f[fa],w=get(x);
son[fa][w]=son[x][w^1];
f[son[fa][w^1]]=fa;
son[x][w^1]=fa;
f[fa]=x;
f[x]=ff;
if(ff) son[ff][son[ff][1]==fa]=x;
}
splay(x) 函数
无数个ratote嵌套
inline void splay(int x){
for(;f[x];rotate(x)){
if(f[f[x]]&&(get(f[x])==get(x)))
rotate(f[x]);
}
root=x;
}
insert(x) 插入函数 x为值
如果是第一个节点就改为root,如果不是就向下找,添加,然后splay它
inline void insert(x){
if(!root){
root=++sz;cnt[sz]=1;son[sz][1]=son[sz][0]=0;key[sz]=x;size[x]=1;
return ;
}
int now=root,fa=0;
while(1){
if(key[now]==x){
cnt[now]++;
update(now);update(fa);
splay(now);
return;
}
fa=now,now=son[fa][key[now]<x];
if(!now){
sz++;
son[sz][1]=son[sz][0]=0;
size[sz]=cnt[sz]=1;
son[fa][key[fa]<x]=sz;
key[sz]=x;
f[sz]=fa;
update(fa);
splay(fa);
return;
}
}
}
未完待续..
3 条评论
wjyyy · 05/06/2018 19:54
加油
Captain_Von · 06/03/2018 19:47
很强,%%%大佬
Captain_Von · 06/03/2018 19:50
%%%%