1.平衡树是一棵二叉查找树。
二叉排序树是一棵空树，或是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
2.平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
例题：bzoj3224/tyvj 1728/luogu 3369 普通平衡树
1.带旋treap
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define nl NULL 5 using namespace std; 6 inline int in(){ 7 int x=0;bool f=0; char c; 8 for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9 for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 10 return f?-x:x; 11 } 12 int n,opt,x; 13 inline int rd(){ 14 static int x=23333; 15 x^=x<<13;x^=x>>17;x^=x<<5;return x; 16 } 17 struct treap{ 18 treap *ls,*rs; 19 int val,pri,num,siz; 20 treap(int val):val(val),pri(rd()),num(1),siz(1),ls(nl),rs(nl){} 21 inline void combine(){siz=(ls?ls->siz:0)+(rs?rs->siz:0)+num;} 22 }*rt; 23 inline void lturn(treap* &x){ 24 treap *y=x->rs;x->rs=y->ls;y->ls=x;y->siz=x->siz;x->combine();x=y; 25 } 26 inline void rturn(treap* &x){ 27 treap *y=x->ls;x->ls=y->rs;y->rs=x;y->siz=x->siz;x->combine();x=y; 28 } 29 inline void ins(treap* &x,int val){ 30 if (x==nl){x=new treap(val);return;} 31 if (val==x->val) x->num++; 32 else if (val>x->val) {ins(x->rs,val);if (x->rs->pri<x->pri) lturn(x);} 33 else {ins(x->ls,val);if(x->ls->pri<x->pri) rturn(x);}x->combine(); 34 } 35 inline void del(treap* &x,int val){ 36 if (x==nl) return; 37 if (val==x->val){ 38 if (x->num>1) x->num--,x->siz--; 39 else if (x->ls==nl||x->rs==nl){ 40 treap *t=x; 41 x=(x->ls==nl)?x->rs:x->ls;delete t; 42 }else if (x->ls->pri<x->rs->pri) rturn(x),del(x,val); 43 else lturn(x),del(x,val); 44 }else if (val<x->val) x->siz--,del(x->ls,val); 45 else x->siz--,del(x->rs,val); 46 } 47 inline int qrank(treap* &x,int val){ 48 if (x==nl) return 0; 49 if (x->ls==nl){ 50 if (val==x->val) return 1; 51 if (val<x->val) return 0; 52 return qrank(x->rs,val)+x->num; 53 }if (val==x->val) return x->ls->siz+1; 54 if (val<x->val) return qrank(x->ls,val); 55 return qrank(x->rs,val)+x->ls->siz+x->num; 56 } 57 inline int qnum(treap *x,int val){ 58 if (x==nl) return 0; 59 if (x->ls==nl){ 60 if (val<=x->num) return x->val; 61 return qnum(x->rs,val-x->num); 62 }if (val<=x->ls->siz) return qnum(x->ls,val); 63 if (val>x->ls->siz+x->num) return qnum(x->rs,val-x->ls->siz-x->num); 64 return x->val; 65 } 66 inline int qpre(treap *x,int val,int ans){ 67 if (x==nl) return ans; 68 if (val>x->val) return qpre(x->rs,val,x->val); 69 return qpre(x->ls,val,ans); 70 } 71 inline int qpost(treap *x,int val,int ans){ 72 if (x==nl) return ans; 73 if (val<x->val) return qpost(x->ls,val,x->val); 74 return qpost(x->rs,val,ans); 75 } 76 int main() 77 { 78 n=in();for (int i=1;i<=n;++i){ 79 opt=in();x=in(); 80 switch (opt){ 81 case 1:ins(rt,x);break; 82 case 2:del(rt,x);break; 83 case 3:printf("%d ",qrank(rt,x));break; 84 case 4:printf("%d ",qnum(rt,x));break; 85 case 5:printf("%d ",qpre(rt,x,-1));break; 86 case 6:printf("%d ",qpost(rt,x,-1));break; 87 } 88 }return 0; 89 }
无旋treap:
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define nl NULL 5 using namespace std; 6 inline int in(){ 7 int x=0;bool f=0; char c; 8 for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9 for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 10 return f?-x:x; 11 } 12 inline int rd(){ 13 static int x=23333; 14 x^=x<<13,x^=x>>17,x^=x<<5;return x; 15 } 16 int n,opt,x; 17 struct treap{ 18 treap *ls,*rs; 19 int val,pri,siz; 20 treap(int val):val(val),pri(rd()),siz(1),ls(nl),rs(nl){} 21 inline void combine(){siz=(ls?ls->siz:0)+(rs?rs->siz:0)+1;} 22 }*rt; 23 typedef pair<treap*,treap*> droot; 24 inline int gsize(treap *x){return x?x->siz:0;} 25 treap *merge(treap *a,treap *b){ 26 if (!a) return b;if (!b) return a; 27 if (a->pri<b->pri){a->rs=merge(a->rs,b);a->combine();return a;} 28 else{b->ls=merge(a,b->ls);b->combine();return b;} 29 }//suppose a<=b 30 droot split(treap *x,int k){ 31 if (!x) return droot(nl,nl);droot y; 32 if (gsize(x->ls)>=k){y=split(x->ls,k);x->ls=y.second;x->combine();y.second=x;} 33 else{y=split(x->rs,k-gsize(x->ls)-1);x->rs=y.first;x->combine();y.first=x;}return y; 34 } 35 inline int qnum(int v){ 36 droot x=split(rt,v-1),y=split(x.second,1); 37 treap *a=y.first;rt=merge(merge(x.first,a),y.second);return a->val; 38 } 39 inline int qrank(treap *x,int v){ 40 if (!x) return 0; 41 if (v<x->val) return qrank(x->ls,v); 42 return qrank(x->rs,v)+gsize(x->ls)+1; 43 } 44 inline void ins(int v){ 45 droot x=split(rt,qrank(rt,v)); 46 treap *a=new treap(v);rt=merge(merge(x.first,a),x.second); 47 } 48 inline void del(int v){ 49 droot x=split(rt,qrank(rt,v)-1),y=split(x.second,1); 50 treap *a=y.first;rt=merge(x.first,y.second);delete a;a=nl; 51 } 52 inline int qpre(int v){return qnum(qrank(rt,v-1));} 53 inline int qsuf(int v){return qnum(qrank(rt,v)+1);} 54 int main() 55 { 56 n=in();for (int i=1;i<=n;++i){ 57 opt=in();x=in();switch (opt){ 58 case 1:ins(x);break; 59 case 2:del(x);break; 60 case 3:printf("%d ",qrank(rt,x-1)+1);break; 61 case 4:printf("%d ",qnum(x));break; 62 case 5:printf("%d ",qpre(x));break; 63 case 6:printf("%d ",qsuf(x));break; 64 } 65 }return 0; 66 }
3.splay