《数据结构》C++代码 Splay
Splay,伸展树。之所以先写这个课内并不怎么常用的数据结构,是因为本人非常喜欢Splay,我觉得这是非常有美感且灵活的一种平衡树。在此先声明,我的伸展树写法来源于CLJ大牛,基础好的同学可以去他的博客中看看他的Splay实现模板,我的实现仅仅借鉴了CLJ大神的一点实现技巧而已。我的博文《心中的大牛博客列表》中有CLJ大神的博客链接。
还有很多同学可能并不了解Splay的思想,那么可以去看sqybi的文章《The magical splay》,百度文库就可以搜索到。这篇文章是我看过的里讲解splay最清晰的。里面的图和讲解都非常棒,里面的代码是Pascal的,但是没关系,只会C++的同学可以看我的代码。
在此先要讲解一下CLJ大神的这个splay实现技巧:充分利用C/C++中将bool型的true和false的值设置为1和0的特点,将树的每个节点的左右孩子指针用如下方式定义——node *son[2]。如此一来,son[0]便是左孩子,son[1]便是右孩子。此时,便可以在实现中,将左侧、右侧操作的代码写成一段,利用一个bool型变量来区分就好了。因此,代码基本会少一半!
我这么说大家肯定糊里糊涂的,不废话了,直接上代码,大家仔细看看代码就懂了。
题目:sjtuoj 1221。
清爽版:暂无。因为Splay的实现代码还是比较长的,因此并不考虑直接写,代码反而会很乱。
类实现版:
/* * 题目:sjtuoj 1221 * oj链接:http://acm.sjtu.edu.cn/OnlineJudge */ #include <iostream> #include <fstream> #include <string> #include <cstdio> using namespace std; const int minInt=1<<31; const int maxInt=minInt-1; struct dot { int c,num,size; dot *son[2],*up; dot(int value=0) { c=value; num=size=1; son[0]=son[1]=up=0; } bool get(dot *lr) { return son[1]==lr; } void add_up(int n) { for(dot *u=this;u;u=u->up) u->size+=n; } dot* born(int k,dot* lr) { son[k]=lr; if(!lr) return this; lr->up=this; add_up(lr->size); return this; } dot* kill(int k) { dot *lr=son[k]; if(!lr) return 0; son[k]=0; lr->up=0; add_up(-lr->size); return lr; } }; int vv(dot *u) { return u?u->c:0; } int ss(dot *u) { return u?u->size:0; } int nn(dot *u) { return u?u->num:0; } class Splay { public: dot *Root,*Min,*Max; private: void zg(dot *x) { dot *y=x->up,*z=y->up; bool i=(z?z->get(y):0),k=y->get(x); if(z) z->kill(i); x->born(!k,y->born(k,y->kill(k)->kill(!k))); if(z) z->born(i,x); if(y==Root) Root=x; // 维护Root,可能也是保险?no!This is useful! } void splay(dot *x,dot *up=0) { dot *y,*z; while(x->up!=up) { y=x->up; if(y->up==up) { zg(x); break; } z=y->up; zg((z->get(y)==y->get(x))?y:x); zg(x); } } void recycle(dot *p) { if(!p) return; recycle(p->son[0]); recycle(p->son[1]); delete p; } dot* next(dot *p,bool k) { splay(p); dot *u=p->son[k]; while(u->son[!k]) u=u->son[!k]; return u; } public: Splay() { Min=Root=new dot(minInt); Max=new dot(maxInt); Min->born(1,Max); } int size() { return Root->size-2; } dot* Find(int c) { dot *u=Root; while(u&&u->c!=c) u=u->son[c>u->c]; return u; } void Insert(int c) { bool k; dot *u=0,*v=Root; while(v&&v->c!=c) { u=v; k=(c>v->c); v=v->son[k]; } if(v) { ++v->num; v->add_up(1); } else splay(u->born(k,new dot(c))->son[k]); } void Delete(int c) { dot *p=Find(c),*l,*r; --p->num; p->add_up(-1); if(p->num==0) { l=next(p,0); r=next(p,1); splay(l); splay(r,Root); recycle(r->kill(0)); } } void Delete(int cl,int cr) { dot *L,*R,*l,*r; Insert(cl); Insert(cr); L=Find(cl); R=Find(cr); l=next(L,0); r=next(R,1); splay(l); splay(r,Root); recycle(r->kill(0)); } int Find_ith(int i,dot *u) // 这里的三种情况,用到了其先后顺序,故顺序不能轻易改变 { int L=ss(u->son[0]),mid=u->num; if(i<=L) return Find_ith(i,u->son[0]); if(i<=L+mid) return u->c; return Find_ith(i-L-1,u->son[1]); } }; Splay A; // 创建一棵Splay树,名叫A int main() { // 本题,假设题目数据均在 minInt+1 ~ maxInt-1 范围内 int n,x,y; cin>>n; string order; for(int i=1;i<=n;++i) { cin>>order; if(order=="insert") { cin>>x; A.Insert(x); } if(order=="delete") { cin>>x; A.Delete(x); } if(order=="delete_less_than") { cin>>y; A.Delete(minInt+1,y-1); } if(order=="delete_greater_than") { cin>>x; A.Delete(x+1,maxInt-1); } if(order=="delete_interval") { cin>>x>>y; A.Delete(x+1,y-1); } if(order=="find") { cin>>x; cout<<(A.Find(x)?"Y":"N")<<endl; } if(order=="find_ith") { cin>>x; if(A.size()<x) { cout<<"N"<<endl; continue; } cout<<A.Find_ith(x+1,A.Root)<<endl; } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。