splay小结—植树结
2018-06-17 23:00:26来源:未知 阅读 ()
我要把高级数据结构当爸爸了... ...弱到跪烂了。
splay,二叉搜索树的一种,具有稳定变形功能。
二叉搜索树:对于一个节点,都只有不超过2个孩子。其左子树内的点的权值都比这个点小,右子树的点的权值都比这个点要大(等于的话随你)。这个性质对于所有点都成立。
我们可以看到二叉搜索树适用于解决求前驱后继、求排名、求第k大等问题。但是如果出题人执(sang)意(xin)要(bing)卡(kuang),造出递减或递增的数据出来,那么你的常规二叉搜索树的每一次插入和查找都是O(n)的,会被时代淘汰的。我们只有提高自己的姿势水平才行。
splay也是一颗二叉搜索树。但是它有个优点:它可以通过旋转节点改变树的形状,江低树的直径,从而江低复杂度。从理论上看,这棵树的深度是logN的,所以一次查询的复杂度就是logN。
那么怎样进行旋转节点就是一个神奇的问题了!
我们要把节点x旋转到它的父亲y的位置,就可以找到规律:
如果x是左儿子,那么y就要变成x的右儿子,x原本的右儿子要变成y的左儿子。
如果x是右儿子,情况是差不多的。
这点东西都很好写,几个if就差不多了(所以常数很大)。关键是旋转技巧。
splay(x,goal),表示江x旋转到goal的儿子处。
如果x是goal的孙子,那么转一次就好了。
不是的话,我们就可以把x转到它的爷爷的位置上面(因为要江低复杂度和树的直径,别问我为什么,问塔尖去)。
你还可以在旋转顺序上做点优化来达到江低直径的效果。
上题。BZOJ书架 操作还是很全的。
但其实初学者还是像我一样先做 codevs营业额统计 比较好,操作较少但splay不少。
改变位置就相当于删除再插入。求排名就是把它splay到顶端然后看左子树大小。
第k本就是第k大,就是二叉搜索树的普通操作。
书架 代码如下。num应该改名成fact,表示点对应的书的编号。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #define LL long long int #define ls (x << 1) #define rs (x << 1 | 1) using namespace std; const int N = 300010; int n,m,T[N],ch[N][2],size[N],num[N]; int fa[N],root,tot,pos[N],rec[N]; int gi() { int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } LL gl() { LL x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } int gsize(int x){return x?size[x]:x;} void up(int x){size[x]=gsize(ch[x][0])+gsize(ch[x][1])+1;} void rtt(int x,int kind) //综合版,包含了zig和zag。 { int y=fa[x],z=fa[y]; ch[y][!kind]=ch[x][kind];fa[x]=z; if(ch[x][kind])fa[ch[x][kind]]=y; if(z) if(ch[z][0]==y)ch[z][0]=x; else ch[z][1]=x; ch[x][kind]=y;fa[y]=x; up(y);up(x); } void splay(int x,int goal) { if(x==goal)return; while(fa[x]!=goal) if(fa[fa[x]]==goal) rtt(x,ch[fa[x]][0]==x); else { int y=fa[x],kind=ch[fa[y]][0]==y; if(ch[y][kind]==x)rtt(x,kind^1),rtt(x,kind); else rtt(y,kind),rtt(x,kind); //听缩这样可以江低复杂度,实际上是的。 } if(goal==0)root=x; } void newnode(int &r,int fat,int x) { r=++tot;fa[tot]=fat;size[tot]=1; ch[tot][0]=ch[tot][1]=0;num[tot]=x;return; } void insert(int rt,int x,int value) //把一个编号为x的书放到位置value上 { if(value==1 && ch[rt][0]==0){newnode(ch[rt][0],rt,x);return;} if(value==2+gsize(ch[rt][0])&&ch[rt][1]==0){newnode(ch[rt][1],rt,x);return;} if(value<=1+gsize(ch[rt][0]))insert(ch[rt][0],x,value); else insert(ch[rt][1],x,value-gsize(ch[rt][0])-1); up(x); } void del(int x) { splay(x,0); if(ch[x][0]==0&&ch[x][1]==0){root=0;return;} if(ch[x][0]==0){root=ch[x][1];fa[root]=0;return;} if(ch[x][1]==0){root=ch[x][0];fa[root]=0;return;} int tmp=ch[x][0];while(ch[tmp][1])tmp=ch[tmp][1]; splay(tmp,x);root=tmp;fa[tmp]=0; ch[tmp][1]=ch[x][1];fa[ch[x][1]]=tmp; up(tmp); } int getsize(int x){splay(x,0);return gsize(ch[x][0])+1;} int gc() { char ch=getchar(); while(ch>'Z' || ch<'A')ch=getchar(); if(ch=='T')return 1; if(ch=='B')return 2; if(ch=='I')return 3; if(ch=='A')return 4; if(ch=='Q')return 5; return 0; } void pr(int x) { printf(" point %d: ls=%d rs=%d size=%d\n",x,ch[x][0],ch[x][1],gsize(x)); if(ch[x][0])pr(ch[x][0]);if(ch[x][1])pr(ch[x][1]); } int find(int x) { int pt=x,r=root; while(1) { if(pt==1+gsize(ch[r][0]))return num[r]; if(pt>1+gsize(ch[r][0]))pt-=(1+gsize(ch[r][0])),r=ch[r][1]; else r=ch[r][0]; } return num[0]; } int main() { n=gi();m=gi(); for(int i=1;i<=n;++i) { rec[i]=gi(); pos[rec[i]]=i; if(i==1)newnode(root,0,rec[1]),root=tot; else{insert(root,rec[i],i);if(i%2)splay(tot,0);} } for(int i=1;i<=m;++i) { int type=gc(),x=gi(),y=type==3?gi():0; switch(type) { case 1:{del(pos[x]);insert(root,x,1);pos[x]=tot;splay(tot,0);break;} case 2:{del(pos[x]);insert(root,x,n);pos[x]=tot;splay(tot,0);break;} case 3:{int S=getsize(pos[x])+y;del(pos[x]);insert(root,x,S);splay(tot,0);pos[x]=tot;break;} case 4:{printf("%d\n",getsize(pos[x])-1);break;} case 5:{printf("%d\n",find(x));break;} default:continue; } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 树结构基础 2020-02-18
- 初级线段树小结 2019-08-26
- 莫队算法例题,模板及小结 2019-08-16
- 第二周学习小结 2018-12-04
- 【阶梯报告】洛谷P3391【模板】文艺平衡树 splay 2018-11-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash