Splay tree 伸展树 (不含区间操作)模板
发布日期:2021-10-02 10:57:29 浏览次数:31 分类:技术文章

本文共 5186 字,大约阅读时间需要 17 分钟。

写了三天的Splay终于AC了,题是用的学校题库里的平衡树的题,由于刚接触Splay,就用那个不含区间操作的练手,结果挂了三天。。这一定会成为黑历史

题目如下:

2183: 普通平衡树

Time Limit: 1 Sec  
Memory Limit: 128 MB

Submit: 269  
Solved: 119

[ ][ ][ ]

Description

此为平衡树系列第一道:普通平衡树您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)

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

 

这个题用啥平衡树都能过,我用Treap和SBT写过,但是Splay要注意的小问题太多了,导致自己一直挂着

比如说每个节点的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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:POJ 2488 A Knight's Journey 水搜索
下一篇:BZOJ 1036 树的统计 树链剖分

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月11日 13时45分52秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行 2019-04-21
redis logfile为空_关于Redis(二) 2019-04-21
mysql 设计两个主键都不可重复_程序员面试备战篇:18个经典MySQL面试专题解析(干货分享答案)... 2019-04-21
下列关于python2.x和3.x的区别说法正确_Python 2.x和Python 3.x版本有哪些区别?【面试题详解】... 2019-04-21
git更换_git命令 2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析 2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件 2019-04-21
android hook sensor数据_最近,又有人在谈论Android的前景了!深入解析趋势及必备技术点... 2019-04-21
python 动态tabel的数据爬取_使用requests爬取python岗位招聘数据 2019-04-21
input js number 整数_JS基础简单小结(1) 2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导 2019-04-21
docker mysql服务启动失败_docker中mysql初始化及启动失败问题解决方案 2019-04-21
mysql 阿里云 添加磁盘空间_rds mysql磁盘空间包含 2019-04-21
mysql 1364 hy000_mysql SQL Error: 1364, SQLState: HY000 保存错误 2019-04-21
mysqli拓展还能用mysql_最近在学习php,其中使用了MYSQLi扩展,注意是MYSQLi不是MYSQL(因PHP7已经不支持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