Splay学习笔记
说在前面：本文多参考这篇优秀博文，讲的十分详细，以下是我个人对Splay的理解。
一、普通Splay
(一)前置知识:
- 前驱:当前序列中小于目标数字的数的最大值
- 后继:当前序列中大于目标数字的数的最小值
- 二叉搜索树BST
(二)变量定义:
ch[u][2]表示第u个节点的两个子节点，其中ch[u][0]表示左子节点,ch[u][1]表示右子节点;- 解释如下的注释
struct Node
{
int val;//当前编号节点的权值
int siz;//以自己(包括自己)为根的树上的节点所存储的值的个数之和(即所有cnt之和)
int cnt;//当前节点上存在数值相等的值的个数
int father;//当前节点的父亲节点
}t[N];
n表示操作数;tot表示平衡树节点总数;root表示根节点编号;
(三)各种操作:
操作一:Insert()[节点插入函数]
inline void Insert(int x)//插入一个值为x的节点
{
int tmp=root,fa=0;
while(tmp&&t[tmp].val!=x)//如果当前节点存在且值不为x
{
fa=tmp;//上一个节点赋值为父亲节点
tmp=ch[tmp][x>t[tmp].val];//x>t[tmp].val可以快捷地判断左右儿子
}
if(tmp)t[tmp].cnt++;//如果存在一个这样的直接累加即可
else
{
tmp=++tot;//添加一个新节点
if(fa)ch[fa][x>t[fa].val]=tmp;//如果有父亲节点则将当前节点作为其子节点
ch[tmp][0]=ch[tmp][1]=0;
t[tmp].cnt=t[tmp].siz=1;
t[tmp].val=x;t[tmp].father=fa;
}
splay(tmp);//将当前节点伸展至根节点
}
操作二:splay()[伸展函数]
inline void splay(int x,int goal=0)//将编号为x的节点伸展至goal的子节点(若不导入参数则goal默认为0即伸展至根节点)
{
while(t[x].father!=goal)//如果还没有伸展至goal的子节点
{
int y=t[x].father;//父亲
int z=t[y].father;//爷爷
if(z!=goal)
{
if(Dir(x)==Dir(y))rotate(y);//一字旋先旋转父亲
else rotate(x);//之字旋先旋转儿子
}
rotate(x);//再次旋转儿子
}
if(!goal)root=x;//如果goal为零则此时x已经是根节点了
}
操作三:rotate()[旋转函数]
大型换爹现场
inline void rotate(int x)//zig和zag的结合版(这部分建议画图理解)
{
int y=t[x].father;//父亲
int z=t[y].father;//爷爷
int k=Dir(x); //1->zag 0->zig
int w=ch[x][k^1];//将x准备用来接上父节点的子树转存
ch[y][k]=w;t[w].father=y;//用转存的子树代替原先x在父节点中的子树
ch[z][Dir(y)]=x;t[x].father=z;//将爷爷的子树赋值为自己
ch[x][k^1]=y;t[y].father=x;//儿子当爹
pushup(y);pushup(x);//上传
}
操作四:Dir()[判断左右儿子函数]
inline bool Dir(int x)//返回当前节点是其父节点的哪个儿子
{
return ch[t[x].father][1]==x;
}
操作五:pushup()[上传函数]
inline void pushup(int k)//更新当前节点的siz值
{
t[k].siz=t[ch[k][0]].siz+t[ch[k][1]].siz+t[k].cnt;
}
操作六:Find()[查找值对应节点的编号并伸展至根节点函数]
inline void Find(int x)
{
int tmp=root;//从根节点开始往下
while(ch[tmp][x>t[tmp].val]&&t[tmp].val!=x)
tmp=ch[tmp][x>t[tmp].val];//没有值为x的节点时则采用其前驱或后继
splay(tmp);
}
操作七:Delete()[删除函数]
inline void Delete(int x)//删除值为x的节点
{
int L=query_pre(x);//找前驱
int R=query_sur(x);//找后继
splay(L);splay(R,L);//将前驱转至根节点,后继作为其右儿子则值为x的节点是后继的左儿子
int del=ch[R][0];
if(t[del].cnt>1)//如果有多个值为x的节点减一即可
{
t[del].cnt--;
splay(del);
}
else ch[R][0]=0;
pushup(R);pushup(root);//上传至祖先节点,注意有顺序性
}
操作八:query_pre()[查找前驱函数]
inline int query_pre(int x)
{
Find(x);//将值为x的节点伸展至根节点
if(t[root].val<x)return root;//若当前节点直接就是x的前驱
int tmp=ch[root][0];
while(ch[tmp][1])tmp=ch[tmp][1];//否则就为左子树中最右边的子节点
splay(tmp);//将答案伸展至根节点
return tmp;
}
操作九:query_sur()[查找后继函数]
inline int query_sur(int x)
{
Find(x);//将值为x的节点伸展至根节点
if(t[root].val>x)return root;//若当前节点直接就是x的后继
int tmp=ch[root][1];
while(ch[tmp][0])tmp=ch[tmp][0];//否则就为右子树中最左边的子节点
splay(tmp);//将答案伸展至根节点
return tmp;
}
操作十:query_rank()[查找排名函数]
inline int query_rank(int x)
{
Find(x);//将值为x的节点伸展至根节点
if(t[root].val<x)return t[ch[root][0]].siz+t[root].cnt;//如果根节点是前驱
return t[ch[root][0]].siz;//如果根节点是自己或者后继
}
操作十一:query_kth()[查找排名为k的值的函数]
inline int query_kth(int k)//需要在主程序中事先加入一个正无穷节点和负无穷节点来规避死循环,所以询问排名为k+1的数实际上返回的是排名为k的数的编号
{
int tmp=root;
while(true)
{
if(k<=t[ch[tmp][0]].siz&&ch[tmp][0])//如果这个数在左子树中
{
tmp=ch[tmp][0];
}
else if(k>t[ch[tmp][0]].siz+t[tmp].cnt)//如果这个数在右子树中
{
k-=t[ch[tmp][0]].siz+t[tmp].cnt;
tmp=ch[tmp][1];
}
else//已经找到
{
splay(tmp);//将当前节点伸展至根节点
return tmp;
}
}
}
(四)完整代码:
#include<bits/stdc++.h>
#define init read()
using namespace std;
const int INF=0x7f7f7f7f;
const int N=100005;
int n,ch[N][2];
int root=0,tot=0;
struct Node
{
int val;
int siz;
int cnt;
int father;
}t[N];
inline int read()
{
int mmm=0,ff=1;char xx=getchar();
while((xx<'0'||xx>'9')&&xx!='-')xx=getchar();
if(xx=='-')ff=-1,xx=getchar();
while(xx>='0'&&xx<='9')
mmm=mmm*10+xx-'0',xx=getchar();
return mmm*ff;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline bool Dir(int x)
{
return ch[t[x].father][1]==x;
}
inline void pushup(int k)
{
t[k].siz=t[ch[k][0]].siz+t[ch[k][1]].siz+t[k].cnt;
}
inline void rotate(int x)
{
int y=t[x].father;
int z=t[y].father;
int k=Dir(x); //1->zag 0->zig
int w=ch[x][k^1];
ch[y][k]=w;t[w].father=y;
ch[z][Dir(y)]=x;t[x].father=z;
ch[x][k^1]=y;t[y].father=x;
pushup(y);pushup(x);
}
inline void splay(int x,int goal=0)
{
while(t[x].father!=goal)
{
int y=t[x].father;
int z=t[y].father;
if(z!=goal)
{
if(Dir(x)==Dir(y))rotate(y);
else rotate(x);
}
rotate(x);
}
if(!goal)root=x;
}
inline void Find(int x)
{
int tmp=root;
while(ch[tmp][x>t[tmp].val]&&t[tmp].val!=x)
tmp=ch[tmp][x>t[tmp].val];
splay(tmp);
}
inline void Insert(int x)
{
int tmp=root,fa=0;
while(tmp&&t[tmp].val!=x)
{
fa=tmp;
tmp=ch[tmp][x>t[tmp].val];
}
if(tmp)t[tmp].cnt++;
else
{
tmp=++tot;
if(fa)ch[fa][x>t[fa].val]=tmp;
ch[tmp][0]=ch[tmp][1]=0;
t[tmp].cnt=t[tmp].siz=1;
t[tmp].val=x;t[tmp].father=fa;
}
splay(tmp);
}
inline int query_pre(int x)
{
Find(x);
if(t[root].val<x)return root;
int tmp=ch[root][0];
while(ch[tmp][1])tmp=ch[tmp][1];
splay(tmp);
return tmp;
}
inline int query_sur(int x)
{
Find(x);
if(t[root].val>x)return root;
int tmp=ch[root][1];
while(ch[tmp][0])tmp=ch[tmp][0];
splay(tmp);
return tmp;
}
inline void Delete(int x)
{
int L=query_pre(x);
int R=query_sur(x);
splay(L);splay(R,L);
int del=ch[R][0];
if(t[del].cnt>1)
{
t[del].cnt--;
splay(del);
}
else ch[R][0]=0;
pushup(R);pushup(root);
}
inline int query_rank(int x)
{
Find(x);
if(t[root].val<x)return t[ch[root][0]].siz+t[root].cnt;
return t[ch[root][0]].siz;
}
inline int query_kth(int k)
{
int tmp=root;
while(true)
{
if(k<=t[ch[tmp][0]].siz&&ch[tmp][0])
{
tmp=ch[tmp][0];
}
else if(k>t[ch[tmp][0]].siz+t[tmp].cnt)
{
k-=t[ch[tmp][0]].siz+t[tmp].cnt;
tmp=ch[tmp][1];
}
else
{
splay(tmp);
return tmp;
}
}
}
inline void print(int x)
{
write(x);putchar('\n');
}
int main()
{
freopen("A2128(Splay).in","r",stdin);
freopen("A2128(Splay).out","w",stdout);
n=init;
Insert(INF);
Insert(-INF);
for(int i=1;i<=n;i++)
{
int opt=init,x=init;
if(opt==1)Insert(x);
else if(opt==2)Delete(x);
else if(opt==3)print(query_rank(x));
else if(opt==4)print(t[query_kth(x+1)].val);
else if(opt==5)print(t[query_pre(x)].val);
else if(opt==6)print(t[query_sur(x)].val);
}
return 0;
}