首页 > 代码库 > 几个平衡树板子
几个平衡树板子
Treap，替罪羊树，splay。跑得不慢，代码在不影响版面的前提下基本已经缩到极限了，不知道还能不能更短。
其实我还会写AVL树，只不过太长懒得写了。反正Treap和替罪羊树跑得也挺快，用用这俩就够了。
话说Treap和替罪羊树都是重量平衡树来着……这倒是方便我了，不过写动态标号的时候到底该写哪个呢……这是个问题……
Treap(普通平衡树)：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 struct node{ 6 static inline int randint(){ 7 static int a=1213857,b=123542441,x=741542853,p=998244353; 8 x=a*x+b;x%=p; 9 return (x<0)?(x+=p):x; 10 } 11 int data,size,p; 12 node *ch[2]; 13 node(int d):data(d),size(1),p(randint()){} 14 void refresh(){size=ch[0]->size+ch[1]->size+1;} 15 int cmp(int x){return x==data?-1:x>data;} 16 }*null=new node(-1),*root=null; 17 void insert(int,node*&); 18 void erase(int,node*&); 19 int order(int,node*); 20 node *kth(int,node*); 21 node *pred(int,node*); 22 node *succ(int,node*); 23 void rot(node*&,int); 24 int n,d,x; 25 int main(){ 26 null->size=0; 27 null->ch[0]=null->ch[1]=null; 28 scanf("%d",&n); 29 while(n--){ 30 scanf("%d%d",&d,&x); 31 if(d==1)insert(x,root); 32 else if(d==2)erase(x,root); 33 else if(d==3)printf("%d\n",order(x,root)); 34 else if(d==4)printf("%d\n",kth(x,root)->data); 35 else if(d==5)printf("%d\n",pred(x,root)->data); 36 else printf("%d\n",succ(x,root)->data); 37 } 38 return 0; 39 } 40 void insert(int x,node *&rt){ 41 if(rt==null){ 42 rt=new node(x); 43 rt->ch[0]=rt->ch[1]=null; 44 return; 45 } 46 int d=abs(rt->cmp(x)); 47 insert(x,rt->ch[d]); 48 rt->refresh(); 49 if(rt->ch[d]->p<rt->p)rot(rt,d^1); 50 } 51 void erase(int x,node *&rt){ 52 int d=rt->cmp(x); 53 if(d==-1){ 54 if(rt->ch[0]!=null&&rt->ch[1]!=null){ 55 d=rt->ch[0]->p<=rt->ch[1]->p; 56 rot(rt,d); 57 erase(x,rt->ch[d]); 58 } 59 else{ 60 node *y=rt->ch[0]!=null?rt->ch[0]:rt->ch[1]; 61 delete rt; 62 rt=y; 63 } 64 } 65 else erase(x,rt->ch[d]); 66 if(rt!=null)rt->refresh(); 67 } 68 int order(int x,node *rt){ 69 int ans=1,d; 70 while(rt!=null){ 71 if((d=x>rt->data))ans+=rt->ch[0]->size+1; 72 rt=rt->ch[d]; 73 } 74 return ans; 75 } 76 node *kth(int k,node *rt){ 77 int d; 78 while(rt!=null){ 79 if(k==rt->ch[0]->size+1)return rt; 80 if((d=k>rt->ch[0]->size+1))k-=rt->ch[0]->size+1; 81 rt=rt->ch[d]; 82 } 83 return null; 84 } 85 node *pred(int x,node *rt){ 86 node *y=null; 87 int d; 88 while(rt!=null){ 89 if((d=x>rt->data))y=rt; 90 rt=rt->ch[d]; 91 } 92 return y; 93 } 94 node *succ(int x,node *rt){ 95 node *y=null; 96 int d; 97 while(rt!=null){ 98 if((d=x<rt->data))y=rt; 99 rt=rt->ch[d^1]; 100 } 101 return y; 102 } 103 void rot(node *&x,int d){ 104 node *y=x->ch[d^1]; 105 x->ch[d^1]=y->ch[d]; 106 y->ch[d]=x; 107 x->refresh(); 108 (x=y)->refresh(); 109 }
随机数生成器以前一直用的二次迭代，后来发现线性迭代随机性也不错，就改用线性迭代了……
替罪羊树(普通平衡树)：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const double alpha=0.7; 6 struct node{ 7 int data,size; 8 node *ch[2]; 9 node(int d):data(d),size(1){} 10 void refresh(){size=ch[0]->size+ch[1]->size+1;} 11 int cmp(int x){return x==data?-1:x>data;} 12 }*null=new node(0),*root=null,*a[100010]; 13 node*& insert(int,node*&); 14 void erase(int,node*&); 15 int order(int,node*); 16 node *kth(int,node*); 17 node *pred(int,node*); 18 node *succ(int,node*); 19 int erase_min(node*&); 20 void travel(node*); 21 void rebuild(int,int,node*&); 22 int n,d,x,cnt; 23 int main(){ 24 null->size=0; 25 null->ch[0]=null->ch[1]=null; 26 scanf("%d",&n); 27 while(n--){ 28 scanf("%d%d",&d,&x);//printf("%d %d\n",d,x); 29 if(d==1){ 30 node *&rt=insert(x,root); 31 if(rt!=null){ 32 cnt=0; 33 travel(rt); 34 rebuild(1,cnt,rt); 35 } 36 } 37 else if(d==2)erase(x,root); 38 else if(d==3)printf("%d\n",order(x,root)); 39 else if(d==4)printf("%d\n",kth(x,root)->data); 40 else if(d==5)printf("%d\n",pred(x,root)->data); 41 else printf("%d\n",succ(x,root)->data); 42 } 43 return 0; 44 } 45 node *&insert(int x,node *&rt){//插入，返回需要重构的节点 46 if(rt==null){ 47 rt=new node(x); 48 rt->ch[0]=rt->ch[1]=null; 49 return null; 50 } 51 int d=abs(rt->cmp(x)); 52 node *&y=insert(x,rt->ch[d]); 53 rt->refresh(); 54 return (max(rt->ch[0]->size,rt->ch[1]->size)>rt->size*alpha)?rt:y; 55 } 56 void erase(int x,node *&rt){//插入时已经维护平衡，删除时不再重构 57 int d=rt->cmp(x); 58 if(d==-1){ 59 if(rt->ch[0]!=null&&rt->ch[1]!=null)rt->data=http://www.mamicode.com/erase_min(rt->ch[1]); 60 else{ 61 node *y=rt->ch[0]!=null?rt->ch[0]:rt->ch[1]; 62 delete rt; 63 rt=y; 64 } 65 } 66 else erase(x,rt->ch[d]); 67 if(rt!=null)rt->refresh(); 68 } 69 int order(int x,node *rt){ 70 int ans=1,d; 71 while(rt!=null){ 72 if((d=x>rt->data))ans+=rt->ch[0]->size+1; 73 rt=rt->ch[d]; 74 } 75 return ans; 76 } 77 node *kth(int k,node *rt){ 78 int d; 79 while(rt!=null){ 80 if(k==rt->ch[0]->size+1)return rt; 81 if((d=k>rt->ch[0]->size))k-=rt->ch[0]->size+1; 82 rt=rt->ch[d]; 83 } 84 return null; 85 } 86 node *pred(int x,node *rt){ 87 node *y=null; 88 int d; 89 while(rt!=null){ 90 if((d=x>rt->data))y=rt; 91 rt=rt->ch[d]; 92 } 93 return y; 94 } 95 node *succ(int x,node *rt){ 96 node *y=null; 97 int d; 98 while(rt!=null){ 99 if((d=x<rt->data))y=rt; 100 rt=rt->ch[d^1]; 101 } 102 return y; 103 } 104 int erase_min(node *&x){ 105 if(x->ch[0]==null){ 106 int tmp=x->data; 107 node *y=x->ch[1]; 108 delete x; 109 x=y; 110 return tmp; 111 } 112 else{ 113 int y=erase_min(x->ch[0]); 114 x->refresh(); 115 return y; 116 } 117 } 118 void travel(node *x){ 119 if(x==null)return; 120 travel(x->ch[0]); 121 a[++cnt]=x; 122 travel(x->ch[1]); 123 } 124 void rebuild(int l,int r,node *&x){ 125 if(l>r){ 126 x=null; 127 return; 128 } 129 int mid=(l+r)>>1; 130 x=a[mid]; 131 rebuild(l,mid-1,x->ch[0]); 132 rebuild(mid+1,r,x->ch[1]); 133 x->refresh(); 134 }
以前写的替罪羊树还要记录父亲，写的长的要死……现在改用引用了，不用记父亲倒是不错，然而插入删除需要全程递归，还是略慢……
把alpha的各种取值都试过了，保守起见选的0.7(真的不敢选太大，怕树高过高查找太慢……)。听lyc说判断失衡的时候+5可以避免小子树多次重构，能提速不少，然而还没试过……
splay(文艺平衡树)：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define dir(x) ((x)==(x)->p->ch[1]) 5 using namespace std; 6 const int maxn=100010; 7 struct node{ 8 int data,size; 9 node *ch[2],*p; 10 bool rev; 11 node(int d=0):data(d),size(1),rev(false){} 12 inline void pushdown(){ 13 if(!rev)return; 14 ch[0]->rev^=true; 15 ch[1]->rev^=true; 16 swap(ch[0],ch[1]); 17 rev=false; 18 } 19 inline void refresh(){size=ch[0]->size+ch[1]->size+1;} 20 }null[maxn],*ptr=null,*root; 21 node *newnode(int); 22 node *build(int,int); 23 void reverse(int,int); 24 void travel(node*); 25 node *kth(int,node* =root); 26 void splay(node*,node* =null); 27 void rot(node*,int); 28 int n,m,l,r; 29 int main(){ 30 null->size=0; 31 null->ch[0]=null->ch[1]=null->p=null; 32 scanf("%d%d",&n,&m); 33 root=build(0,n+1); 34 while(m--){ 35 scanf("%d%d",&l,&r); 36 reverse(l,r); 37 } 38 travel(root); 39 return 0; 40 } 41 node *newnode(int d){ 42 node *x=++ptr; 43 *x=node(d); 44 x->ch[0]=x->ch[1]=x->p=null; 45 return x; 46 } 47 node *build(int l,int r){ 48 if(l>r)return null; 49 int mid=(l+r)>>1; 50 node *x=newnode(mid); 51 if((x->ch[0]=build(l,mid-1))!=null)x->ch[0]->p=x; 52 if((x->ch[1]=build(mid+1,r))!=null)x->ch[1]->p=x; 53 x->refresh(); 54 return x; 55 } 56 void reverse(int l,int r){ 57 splay(kth(l-1)); 58 splay(kth(r+1),root); 59 root->ch[1]->ch[0]->rev^=true; 60 } 61 void travel(node *x){ 62 if(x==null)return; 63 x->pushdown(); 64 travel(x->ch[0]); 65 if(x->data>0&&x->data<=n)printf("%d ",x->data); 66 travel(x->ch[1]); 67 } 68 node *kth(int k,node *rt){ 69 int d; 70 k++; 71 while(rt!=null){ 72 rt->pushdown(); 73 if(k==rt->ch[0]->size+1)return rt; 74 if((d=k>rt->ch[0]->size))k-=rt->ch[0]->size+1; 75 rt=rt->ch[d]; 76 } 77 return null; 78 } 79 void splay(node *x,node *tar){ 80 while(x->p!=tar){ 81 if(x->p->p==tar){ 82 rot(x->p,dir(x)^1); 83 break; 84 } 85 if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1); 86 else rot(x->p,dir(x)^1); 87 rot(x->p,dir(x)^1); 88 } 89 } 90 void rot(node *x,int d){ 91 node *y=x->ch[d^1]; 92 if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x; 93 if((y->p=x->p)!=null)x->p->ch[dir(x)]=y; 94 else root=y; 95 (y->ch[d]=x)->p=y; 96 x->refresh(); 97 y->refresh(); 98 }
旋转里面括号里的那几个赋值以前都是单独写一句的，今天发现可以用括号括起来缩掉三行，然后就这么改了……
话说好像无论null的左右儿子是否赋值为null都可以过题，不过保守起见还是赋值一下好了……
想当年自己打一个平衡树要费0.5+h乃至1+h，现在写平衡树最多15min，666666……
几个平衡树板子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。