此为平衡树系列第一道:普通平衡树您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)
Splay tree 伸展树 (不含区间操作)模板
Submit: 269 Solved: 119
[ ][ ][ ] 这个题用啥平衡树都能过,我用Treap和SBT写过,但是Splay要注意的小问题太多了,导致自己一直挂着
发布日期:2021-10-02 10:57:29
浏览次数:31
分类:技术文章
本文共 5186 字,大约阅读时间需要 17 分钟。
写了三天的Splay终于AC了,题是用的学校题库里的平衡树的题,由于刚接触Splay,就用那个不含区间操作的练手,结果挂了三天。。这一定会成为黑历史
题目如下:
2183: 普通平衡树
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 269 Solved: 119
[ ][ ][ ]
Description
Input
第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数,表示对应答案
Sample Input
8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1
Sample Output
2
20
20
20
HINT
n<=100000 所有数字均在-107到107内
比如说每个节点的father域和son域在更新的时候千万不要忘记更新father域,我就是在这个问题上一直挂着,好孩子千万不要像我学习啊!!
旋转操作:
右旋操作:
右旋+左旋 \ 左旋+右旋
配合上面的图片理解动笔画画应该能很快理解Splay平衡的原理
代码:
#include#include #include #include #define INF 0x7f7f7f7fusing namespace std; struct Complex{ int val,cnt,size; Complex *son[2],*father; void Maintain(); int Compare(int x) { if(x == val) return -1; return x > val; } bool Check() { return father->son[1] == this; }}none,*nil = &none,*root = nil; inline void Splay(Complex *x,Complex *aim);inline void Rotate(Complex *x,bool dir);inline void Insert(int x);void Update(Complex *now);inline Complex *NewNode(Complex *f,int val);void Delete(Complex*& a,int x);inline Complex *Find(int x);int Find(Complex* a,int x);int FindK(Complex *a,int k);int FindPred(Complex *a,int x);int FindSucc(Complex *a,int x); int main(){ nil->son[0] = nil->son[1] = nil; nil->father = nil; nil->size = nil->cnt = 0; int cnt; cin >> cnt; for(int flag,x,i = 1;i <= cnt; ++i) { scanf("%d%d",&flag,&x); switch(flag) { case 1:Insert(x);break; case 2:Delete(root,x);break; case 3:printf("%d\n",Find(root,x));break; case 4:printf("%d\n",FindK(root,x));break; case 5:printf("%d\n",FindPred(root,x));break; case 6:printf("%d\n",FindSucc(root,x));break; } } return 0;} void Complex :: Maintain(){ if(this == nil) return ; size = cnt + son[0]->size + son[1]->size;} inline void Splay(Complex *x,Complex *aim){ while(x->father != aim) { if(x->father->father == aim) { if(!x->Check()) Rotate(x,true); else Rotate(x,false); } else if(!x->father->Check()) { if(!x->Check()) { Rotate(x->father,true); Rotate(x,true); } else { Rotate(x,false); Rotate(x,true); } } else { if(x->Check()) { Rotate(x->father,false); Rotate(x,false); } else { Rotate(x,true); Rotate(x,false); } } x->Maintain(); }} inline void Rotate(Complex *x,bool dir){ Complex *f = x->father; f->son[!dir] = x->son[dir]; f->son[!dir]->father = f; x->son[dir] = f; x->father = f->father; if(f->father->son[0] == f) f->father->son[0] = x; else f->father->son[1] = x; f->father = x; f->Maintain(),x->Maintain(); if(root == f) root = x;} inline void Insert(int x){ if(root == nil) { root = NewNode(nil,x); return ; } Complex *now = root; while(true) { int dir = now->Compare(x); if(dir == -1) { now->cnt++; Update(now); return ; } else if(now->son[dir] != nil) now = now->son[dir]; else { now->son[dir] = NewNode(now,x); Update(now); Splay(now->son[dir],nil); return ; } }} void Update(Complex* now){ now->Maintain(); if(now != root) Update(now->father);} inline Complex *NewNode(Complex* f,int val){ Complex *re = new Complex(); re->cnt = re->size = 1; re->val = val; re->son[0] = re->son[1] = nil; re->father = f; return re;}void Delete(Complex*& a,int x){ int dir = a->Compare(x); if(dir != -1) Delete(a->son[dir],x); else { if(a->cnt > 1) a->cnt--; else { if(a->son[0] == nil) a->son[1]->father=a->father, a = a->son[1]; else if(a->son[1] == nil) a->son[0]->father=a->father, a = a->son[0]; else { Rotate(a->son[0],true); Delete(a->son[1],x); } } } if(a != nil) a->Maintain();} inline Complex *Find(int x){ Complex *now = root; while(true) { int dir = now->Compare(x); if(dir == -1) return now; now = now->son[dir]; }}int Find(Complex *a,int x){ int re = a->son[0]->size; int dir = a->Compare(x); if(!dir) return Find(a->son[0],x); if(dir == -1) return re + 1; return re + a->cnt + Find(a->son[1],x);} int FindK(Complex *a,int k){ int l = a->son[0]->size; if(k <= l) return FindK(a->son[0],k); k -= l; if(k <= a->cnt) return a->val; k -= a->cnt; return FindK(a->son[1],k);} int FindPred(Complex* a,int x){ if(a == nil) return -INF; if(x <= a->val) return FindPred(a->son[0],x); return max(a->val,FindPred(a->son[1],x));} int FindSucc(Complex* a,int x){ if(a == nil) return INF; if(x >= a->val) return FindSucc(a->son[1],x); return min(a->val,FindSucc(a->son[0],x));}
转载地址:https://blog.csdn.net/jiangyuze831/article/details/38983199 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月11日 13时45分52秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
python双击py一闪_Python脚本在双击.py时无法正常运行
2019-04-21
redis logfile为空_关于Redis(二)
2019-04-21
git更换_git命令
2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析
2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件
2019-04-21
python 动态tabel的数据爬取_使用requests爬取python岗位招聘数据
2019-04-21
input js number 整数_JS基础简单小结(1)
2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导
2019-04-21
mysql 阿里云 添加磁盘空间_rds mysql磁盘空间包含
2019-04-21
java中gui_java中GUI是什么意思?详细图解
2019-04-21
java iso 8601_如何在iOS上获得ISO 8601日期?
2019-04-21
windows8怎么下载python_win8怎么安装python
2019-04-21
linux猜数字程序,用linux实现猜数字小游戏源码
2019-04-21