首页 > 代码库 > 自己yy的Splay
自己yy的Splay
#include <iostream> #include <cstdio> #include <queue> using namespace std; const int maxn=1e5+7; struct Node{ int val,rev,max,min; Node(){} Node(int _rev,int _max,int _min){ this->rev=_rev; this->max=_max; this->min=_min; } }; Node node[maxn]; int son[maxn][2];//0 表示左儿子,1表示右儿子 int father[maxn]; bool Root[maxn]; int ROOT; int tot; int n,q,op; struct bnode{ int v,dep; bnode(int _v,int _dep){ this->v=_v; this->dep=_dep; } }; vector<int> DEEP[maxn]; void init(){ tot=1; ROOT=-1; memset(Root,0,sizeof(Root)); } void BFS(){ int i; for(i=0;i<maxn;++i){ DEEP[i].clear(); } if(ROOT==-1) return; queue<bnode> que; que.push(bnode(ROOT,1)); while(!que.empty()){ bnode t=que.front(); que.pop(); int v=t.v; int dep=t.dep; DEEP[dep].push_back(v); if(son[v][0]!=0) que.push(bnode(son[v][0],dep+1)); if(son[v][1]!=0) que.push(bnode(son[v][1],dep+1)); } } void print(){ BFS(); int cnt=0; for(int j=1;j<30;++j){ if(DEEP[j].size()==0) break; cnt++; printf("DEEP:%d==>",j); for(int k=0;k<DEEP[j].size();++k){ printf("%d ",DEEP[j][k]); } printf("\n"); } if(!cnt) printf("The Tree is Empty\n"); } void printVAL(){ int i; for(i=1;i<tot;++i){ printf("v%d val%d leftson%d rightson%d fa%d\n",i,node[i].val,son[i][0],son[i][1],father[i]); } } void zig(int x){ int y=father[x]; int z=father[y]; son[y][0]=son[x][1]; if(son[x][1]!=0) father[son[x][1]]=y; son[x][1]=y; if(y!=0) father[y]=x; if(x!=0) father[x]=z; if(z!=-1&&z!=0){ if(son[z][0]==y){ son[z][0]=x; } else { son[z][1]=x; } } if(Root[y]){ Root[x]=true; Root[y]=false; ROOT=x; } } void zag(int x){ int y=father[x]; int z=father[y]; son[y][1]=son[x][0]; if(son[x][0]) father[son[x][0]]=y; son[x][0]=y; if(y) father[y]=x; if(x) father[x]=z; if(z!=-1&&z!=0){ if(son[z][0]==y){ son[z][0]=x; } else{ son[z][1]=x; } } if(Root[y]){ Root[x]=true; Root[y]=false; ROOT=x; } } void zigzig(int x){ int y=father[x]; zig(y); zig(x); } void zagzag(int x){ int y=father[x]; zag(y); zag(x); } void zigzag(int x){ zig(x);zag(x); } void zagzig(int x){ zag(x);zig(x); } void Splay(int x){ while(!Root[x]){ int y=father[x]; int z=father[y]; if(z!=-1&&!Root[z]){ if(son[z][0]==y){ if(son[y][0]==x){ zigzig(x); } else{ zag(x);zig(x); } } if(son[z][1]==y){ if(son[y][1]==x){ zagzag(x); } else{ zig(x);zag(x); } } } else if(!Root[y]){ if(son[y][0]==x){ zig(x); } else{ zag(x); } } else { if(son[y][0]==x){ zig(x); } else { zag(x); } } // printf("==========\n"); // print(); // printVAL(); } } int insert(int rt,int x){ if(rt==-1){ rt=tot; node[rt].val=x; father[rt]=-1; Root[rt]=true; ROOT=rt; ++tot; return tot-1; } if(x>node[rt].val){ if(son[rt][1]==0){ node[tot].val=x; father[tot]=rt; son[rt][1]=tot; tot++; return tot-1; } else insert(son[rt][1],x); } else if(x<node[rt].val){ if(son[rt][0]==0){ node[tot].val=x; father[tot]=rt; son[rt][0]=tot; tot++; return tot-1; } else insert(son[rt][0],x); } } int Search(int rt,int x){ // printf("rt%d x%d\n",rt,x); if(rt==-1){ //Exception } if(x==node[rt].val){ Splay(rt); return rt; } if(x>node[rt].val){ if(son[rt][1]==0) return -1; return Search(son[rt][1],x); } else if(x<node[rt].val){ if(son[rt][0]==0) return -1; return Search(son[rt][0],x); } } int SearchMax(int rt){ if(son[rt][1]!=0){ int x=son[rt][1]; if(son[x][1]==0) return x; return SearchMax(son[x][1]); } return rt; } bool Delete(int x){ int id=Search(ROOT,x); if(id==-1) return false; Splay(id); // print(); // printf("=======\n"); int left=son[id][0]; int right=son[id][1]; son[id][0]=0; son[id][1]=0; if(left) father[left]=-1; if(right) father[right]=-1; Root[id]=false; if(left) Root[left]=true; if(left) ROOT=left; if(left){ int lmx=SearchMax(left); // printf("left%d lmx%d\n",left,lmx); // print(); Splay(lmx); son[lmx][1]=right; father[right]=lmx; father[lmx]=-1; Root[id]=false; Root[lmx]=true; ROOT=lmx; } else if(right){ father[right]=-1; Root[id]=false; Root[right]=true; ROOT=right; } else{ init(); } return true; // print(); } int findRoot(){ } void INSERT(int rt,int x){ int id=insert(rt,x); printf("After insert\n"); print(); Splay(id); printf("After Splay\n"); print(); } int main(){ init(); scanf("%d%d",&n,&q); //少写一个%d int i,x; for(i=0;i<n;++i){ scanf("%d",&x); INSERT(ROOT,x); } // printVAL(); for(i=0;i<q;++i){ scanf("%d",&op); if(op==1){ scanf("%d",&x); INSERT(ROOT,x); } else if(op==2){ scanf("%d",&x); int r=Delete(x); if(r){ printf("Delete %d successful\n",x); } else printf("NOT FIND %d\n",x); } else if(op==3){ scanf("%d",&x); int id; // print(); if((id=Search(ROOT,x))!=-1){ printf("%d FIND v is %d\n",x,id); } else{ printf("%d NOT FIND\n",x); } } else if(op==4){ // printf("there22\n"); // printVAL(); print(); } } return 0; }
自己yy的Splay
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。