tyvj 普通平衡树 SBT or splay

普通平衡树 From admin     背景 Background 此为平衡树系列第一道：普通平衡树     描述 Description 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)     输入格式 InputFormat 第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)     输出格式 OutputFormat 对于操作3,4,5,6每行输出一个数，表示对应答案     样例输入 SampleInput [复制数据] 8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1     样例输出 SampleOutput [复制数据] 2 20 20 20     数据范围和注释 Hint n<=100000 所有数字均在-10^7到10^7内   数据结构水题+裸题 第一次敲是splay，有点手生。这种题站一下代码就行了，我用SBT和splay各编了一遍。   在这里总结一下splay易错（重要）的几点： 1、如需垃圾回收，放在队列中的必须是指针，这次我拿数组下标存的，发现根本无法回收，觉得太麻烦，就没改了 2、可通过一个nil空节点代替NULL，简便了便捷判断 3、rotate函数调用update()一定要按照调整后的顺序自底向上 4、splay（）部分不怎么理解，还要硬背 5、splay（）最后注意更新root值 6、所有平衡树都存在的乱转size值的问题，这次问题出现在get_val()中 7、delete（）中要单独处理儿子为nil的值 8、delete（）注意新root节点的father指针改为nil 9、get_min（）判断now==nil情况 10、一些小的马虎错误   #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<cstdio> using namespace std; #define MAXT 1000000 #define INF 0x3f3f3f3f int n,m; struct SBTree { int L[MAXT],R[MAXT],K[MAXT],S[MAXT]; queue<int> Q; int root; SBTree() { root=0; int i; for (i=1;i<MAXT;i++) { Q.push(i); } } void update(int &now) { S[now]=S[L[now]]+S[R[now]]+1; } void r_rotate(int &now) { int t=L[now]; L[now]=R[t];update(now); R[t]=now;update(t); now=t; } void l_rotate(int &now) { int t=R[now]; R[now]=L[t];update(now); L[t]=now;update(t); now=t; } void maintain(int &now) { if (S[L[L[now]]]>S[R[now]]) { r_rotate(now); maintain(L[now]); maintain(R[now]); maintain(now); return; } if (S[R[R[now]]]>S[L[now]]) { l_rotate(now); maintain(L[now]); maintain(R[now]); maintain(now); return; } if (S[L[R[now]]]>S[L[now]]) { r_rotate(R[now]); l_rotate(now); maintain(L[now]); maintain(R[now]); maintain(now); return; } if (S[R[L[now]]]>S[R[now]]) { l_rotate(L[now]); r_rotate(now); maintain(L[now]); maintain(R[now]); maintain(now); return; } } void Insert(int &now,int v) { if (!now) { now=Q.front(); Q.pop(); L[now]=R[now]=0; S[now]=1; K[now]=v; return ; } if (v<=K[now]) { Insert(L[now],v); }else { Insert(R[now],v); } update(now); maintain(now); } void Delete(int &now,int x) { // if (!now) throw 1; if (!now) return ; if (K[now]==x) { if (!L[now]&&!R[now]) { Q.push(now); now=0; return ; } if (!L[now]) { Q.push(now); now=R[now]; return ; } if (!R[now]) { Q.push(now); now=L[now]; return ; } r_rotate(now); Delete(R[now],x);/**/ update(now); maintain(now); return ; } if (x<K[now]) { Delete(L[now],x); }else { Delete(R[now],x); } update(now); maintain(now); } int get_val(int &now,int rk) { if (rk==S[L[now]]+1) { return K[now]; } if (rk<=S[L[now]]) { return get_val(L[now],rk); }else { return get_val(R[now],rk-S[L[now]]-1); } } int get_rank(int &now,int x) { if (!now)return INF; if (x==K[now]) { return min(S[L[now]]+1,get_rank(L[now],x)); } if (x<K[now]) { return get_rank(L[now],x); }else { return get_rank(R[now],x)+S[L[now]]+1; } } int get_prev(int &now,int v) { if (!now)return -INF; if (K[now]<v) { return max(K[now],get_prev(R[now],v)); }else { return get_prev(L[now],v); } } int get_next(int &now,int v) { if (!now)return INF; if (K[now]>v) { return min(K[now],get_next(L[now],v)); }else { return get_next(R[now],v); } } void Scan(int &now) { if (!now)return ; if (S[now]!=S[L[now]]+S[R[now]]+1) { throw 1; } Scan(L[now]); printf("%d ",K[now]); Scan(R[now]); } }SBT; int main() { // freopen("input.txt","r",stdin); // freopen("output1.txt","w",stdout); int i,x,opt; scanf("%d",&m); for (i=0;i<m;i++) { scanf("%d%d",&opt,&x); // cout<<x<<":"<<endl; switch (opt) { case 1: SBT.Insert(SBT.root,x); // SBT.Scan(SBT.root);cout<<endl; break; case 2: SBT.Delete(SBT.root,x); // SBT.Scan(SBT.root);cout<<endl; break; case 3: printf("%d\n",SBT.get_rank(SBT.root,x)); break; case 4: printf("%d\n",SBT.get_val(SBT.root,x)); break; case 5: printf("%d\n",SBT.get_prev(SBT.root,x)); break; case 6: printf("%d\n",SBT.get_next(SBT.root,x)); break; } } return 0; }

 

  #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<cstdio> using namespace std; #define MAXT 1000000 #define INF 0x3f3f3f3f struct node { int val,cnt,siz; node* fa,*ch[2]; node(){} node(int a,int b,int c) { val=a;cnt=b;siz=c; } void update() { siz=ch[1]->siz+ch[0]->siz+cnt; } }; node nil_node(0,0,0),*nil=&nil_node; struct Splay_tree { node *root; int ncnt; node E[MAXT]; queue<int> Q; Splay_tree() { root=nil; ncnt=0; int i; for (i=1;i<MAXT;i++) { Q.push(i); } } node* new_node(int key) { int now=Q.front(); Q.pop(); E[now].val=key; E[now].cnt=E[now].siz=1; E[now].ch[0]=E[now].ch[1]=nil; return &E[now]; } void rotate(node *now,int pp) { node *y=now->fa; y->ch[!pp]=now->ch[pp]; if (now->ch[pp]!=nil)now->ch[pp]->fa=y; now->fa=y->fa; if (y->fa!=nil)/**/ { if (y->fa->ch[0]==y) { y->fa->ch[0]=now; }else { y->fa->ch[1]=now; } } y->fa=now; now->ch[pp]=y; y->update(); now->update();/**/ } void Splay(node* now,node *top) { if (now==top||now==nil)return; node *y; while (now->fa!=top) { y=now->fa; if (now==y->ch[0]) { if (y->fa!=top&&y==y->fa->ch[0])rotate(now,1); rotate(now,1); }else { if (y->fa!=top&&y==y->fa->ch[1])rotate(now,0); rotate(now,0); } } if (top==nil) { root=now; } } void Insert(int key) { node* now,*x; now=root; if (root==nil) { root=new_node(key); x=root; root->fa=nil; return ; } while(1) { now->siz++; if (now->val==key) { x=now;/**/ now->cnt++; break; } if (key<now->val) { if (now->ch[0]==nil) { now->ch[0]=new_node(key); now->ch[0]->fa=now; x=now->ch[0]; break; }else { now=now->ch[0]; continue; } } if (key>now->val) { if (now->ch[1]==nil) { now->ch[1]=new_node(key); now->ch[1]->fa=now; x=now->ch[1]; break; }else { now=now->ch[1]; continue; } } } Splay(x,nil); } void Delete(node *now) { if (now==nil) { throw "fuck"; } if (now->cnt>1) { now->siz--; now->cnt--; while (now!=root) { now=now->fa; now->siz--; } return ; } Splay(now,nil); if (now->ch[0]==nil) { root=now->ch[1]; now->ch[1]->fa=nil; return ; } if (now->ch[1]==nil) { root=now->ch[0]; now->ch[0]->fa=nil; return ; } Splay(get_min(now->ch[0]),root); Splay(get_min(now->ch[1]),root); now->ch[1]->ch[0]=now->ch[0]; now->ch[0]->fa=now->ch[1]; now->ch[1]->fa=nil; root=now->ch[1]; root->update(); } node* get_min(node* now) { if (now==nil)return now; while (now->ch[0]!=nil)now=now->ch[0]; return now; } node *search(int key) { node *now; now=root; while (1) { if (now->val==key) { return now; } if (key<now->val) { now=now->ch[0]; }else { now=now->ch[1]; } } return nil; } int get_rank(int key) { Splay(search(key),nil); return root->ch[0]->siz+1; } int get_val(node *now,int rank) { if (rank<=now->ch[0]->siz) { return get_val(now->ch[0],rank); } if (rank>now->ch[0]->siz+now->cnt) { return get_val(now->ch[1],rank-now->ch[0]->siz-now->cnt); } return now->val; } int prev(node *now,int key) { int ret=-INF; if (now==nil)return -INF; if (key>now->val) { return max(prev(now->ch[1],key),now->val); } if (key<=now->val) { return prev(now->ch[0],key); } } int next(node *now,int key) { if (now==nil)return INF; if (key<now->val) { return min(next(now->ch[0],key),now->val); } if (key>=now->val) { return next(now->ch[1],key); } } void Scan(node* now) { if (now==nil) { return ; } if (now->ch[0]!=nil && now->ch[0]->fa!=now)cout<<"Error_a"; if (now->ch[1]!=nil && now->ch[1]->fa!=now)cout<< "Error_b"; if (now->siz!=now->ch[0]->siz+now->ch[1]->siz+now->cnt)cout<<"Error_c"; Scan(now->ch[0]); printf("%d[%d] ",now->val,now->cnt); Scan(now->ch[1]); } }spt; int n,m; int main() { // freopen("input.txt","r",stdin); // freopen("output1.txt","w",stdout); int i,x,opt; scanf("%d",&m); for (i=0;i<m;i++) { scanf("%d%d",&opt,&x); switch (opt) { case 1: spt.Insert(x); break; case 2: spt.Delete(spt.search(x)); break; case 3: printf("%d\n",spt.get_rank(x)); break; case 4: printf("%d\n",spt.get_val(spt.root,x)); break; case 5: printf("%d\n",spt.prev(spt.root,x)); break; case 6: printf("%d\n",spt.next(spt.root,x)); break; } // spt.Scan(spt.root);cout<<endl; } return 0; }

 

 

转载于:https://www.cnblogs.com/mhy12345/p/3793658.html