[复习]平衡树splay
2024-09-06 11:18:02
明天要考试了……
出来写一个splay的复习总结。
怕忘……
^废话^
以下内容学习自yyb大神的博客,
由于yyb大神内容不全,
部分是博主本人自行脑补。。。
这个模板还是比较全的^-^
^又是一堆不是废话的废话^
Splay的核心就是旋转了。
rotate操作:将x旋转为它祖先节点的子节点。
inline void rotate(long long x)//基本旋转操作:旋转x
{
long long y=t[x].fa,z=t[y].fa,k=t[y].ch[]==x;//y是x的父节点,z是x的祖先节点,
//k存储x是y的哪一个儿子
t[z].ch[t[z].ch[]==y]=x;
t[x].fa=z;//祖为父:我变成我爷爷的儿子,我管我爷爷喊爸爸
t[y].ch[k]=t[x].ch[k^];
t[t[x].ch[k^]].fa=y;//子为孙:我儿子过继给我爸爸,我儿子管我爸爸喊爹
t[x].ch[k^]=y;
t[y].fa=x;//父为子:我爸爸变成我儿子,我爸爸管我喊爹
t[y].size=t[t[y].ch[]].size+t[t[y].ch[]].size+t[y].cnt;//更新节点规模
//size存储以该节点为根节点的子树的大小(包括自身)
t[x].size=t[t[x].ch[]].size+t[t[x].ch[]].size+t[x].cnt;//由于此时y是x的子节点,所以先y后x
}
涉及伦理问题……引起不适敬请原谅
splay操作:将x旋转为goal的子节点
inline void splay(long long x,long long goal)//splay操作:将x旋转为goal的子节点
{
while(t[x].fa!=goal)//若x的父节点不是目标节点
{
long long y=t[x].fa,z=t[y].fa;//取出父节点和祖先节点
if(z!=goal)//若祖先节点依旧不是目标节点,那么意味着我们至少需要旋转两次
(t[z].ch[]==y)^(t[y].ch[]==x)?rotate(x):rotate(y);
//为了打乱原本平衡树上存在的一条链从而防止被卡,若x、y、z在同一条线上,先转y
rotate(x);//无论之前转了y还是x或者是没有转,我们都需要再转一次x
}
if(!goal)root=x;//更新根节点
}
insert操作:插入一个数x,使平衡树仍然保持平衡
inline void insert(long long x)//插入操作:插入一个数x,使平衡树仍然保持平衡
{
long long u=root,fa=;//从根节点开始搜,记得存储fa以更新x的节点信息中的fa
while(u&&t[u].data!=x)//u仍然存在且当前节点u不等于目标节点,迭代向下查找。
{
fa=u;
u=t[u].ch[x>t[u].data];//x小于当前节点信息,向左查找,否则向右查找。(利用平衡树本身性质)
}
if(u)t[u].cnt++;//如果本身存在该节点,该节点个数加一
else //否则新建一个节点(各个信息都要新建)
{
u=++tot;
if(fa)t[fa].ch[x>t[fa].data]=u;
t[u].ch[]=t[u].ch[]=;
t[tot].fa=fa;
t[tot].data=x;
t[tot].cnt=;
t[tot].size=;
}
splay(u,);
}
find操作:找到元素x并将它旋转为根节点
inline void find(long long x)//查找操作:找到元素x并将它旋转为根节点
{
long long u=root;//u是当前节点,从根节点开始搜索。
if(!u)return ;//如果没有根节点,即没有树:查询无效。
while(t[u].ch[x>t[u].data]&&x!=t[u].data)//继续迭代向下查找x
u=t[u].ch[x>t[u].data];
splay(u,);//转上去
}
nxt操作:查询前驱或后继
inline long long nxt(long long x,long long jud)//查询操作:查询前驱或后继
{ //(jud为0时表示查询前驱,jud为1时表示查询后继)
find(x);//找到x并把他(或者和它最接近的那个点)转到根节点
long long u=root;
if(t[u].data>x&&jud)return u;
if(t[u].data<x&&!jud)return u;//这两句话针对查询的x本身不在平衡树中
u=t[u].ch[jud];//若该节点已经被旋转为根节点,前驱是它左子树最右边的儿子,后驱是它右子树最左边的儿子。
while(t[u].ch[jud^])u=t[u].ch[jud^];
return u;
}
delet操作:删掉某一个节点
inline void delet(long long x)//删除操作:删掉某一个节点
{
long long pre=nxt(x,);
long long nt=nxt(x,);//分别查询前驱和后继并存储
splay(pre,),splay(nt,pre);//把前驱转成根节点,把后继转成根节点的子节点。
//分析可得此时nt是pre的右儿子,x是nt的左儿子且x没有子树
long long res=t[nt].ch[];
if(t[res].cnt>)
{
t[res].cnt--;//若该节点不止一个,删掉一个
splay(res,);//并把该节点旋转至根节点
}
else t[nt].ch[]=;//否则直接把它扔掉(nt的左儿子指向空)
}
k_th操作:查询已插入的节点中第k大的数
inline long long k_th(long long x)//第k大操作:查询已插入的节点中第k大的数
{
long long u=root;//临时节点u
if(t[u].size<x)return ;//若该点的规模小于x,即不可能存在第x大的数,返回0
while()
{
int y=t[u].ch[];//取出左儿子方便查询规模
if(x>t[y].size+t[u].cnt)//如果所查询的数大于左儿子的规模
{
x-=t[y].size+t[u].cnt;//往右找,查询的第k大数即是右儿子中x-t[y].size+t[u].cnt
u=t[u].ch[];
}
else
if(t[y].size>=x) u=y;//如果儿子查询
else return t[u].data;//
}
}
谢谢您的一波关注好评阅读评论走起~
最新文章
- Javascript原型继承 __proto__
- [SQL入门级] 接上篇,继续查询
- 转:AJAX中xhr对象详解
- javascript中的克隆
- UI Automation Test
- html部分---样式属性;
- MySQL数据的主从复制、半同步复制和主主复制详解-转
- vimrc示例
- HDU 4348 To the moon 可持久化线段树,有时间戳的区间更新,区间求和
- DLL远程注入与卸载
- 面试题总结之Database
- TOKEN+签名验证
- Decorator Wrapper 装饰模式 包装
- java 文件操作 读取txt文本(兄弟常开心)
- codeforces#439 D. Devu and his Brother (二分)
- react-redux异步数据操作
- Ubuntu18.04安装网易云音乐
- ajax与文件上传
- EF 跨库查询
- BZOJ1406 [AHOI2007]密码箱 数论