平衡树Treap模板与原理
这次我们来讲一讲Treap(splay以后再更)
平衡树是一种排序二叉树(或二叉搜索树)，所以排序二叉树可以迅速地判断两个值的大小，当然操作肯定不止那么多(不然我们还学什么)。
而平衡树在排序二叉树的基础上主要是增加了一个优化：就是高度较为平衡，并可以动态平衡。
而今天要讲的treap就是一种动态平衡的方法。
首先说声抱歉，因为没有那么多的时间，所以无法把左旋和右旋两种操作具体的讲，但是可以看刘汝佳的蓝书，讲得还是挺清楚的。
现在开始。
treap用的是一种比较玄学的方法，就是将每一个点还附上一个随机值，然后按照堆的性质，不管大小根堆都是一样的，所以我们每加入一个值，就利用上浮操作进行旋转，保持堆的性质，且不改变排序二叉树的性质。
操作很好理解，就是每次insert时进行判断就行了，若不满足，则上浮。
具体的排序二叉树的操作，我就不再赘述了，如果要学，可以看刘汝佳的蓝书(感觉在跟刘汝佳打广告)。
下面送上代码。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<ctime> 6 using namespace std; 7 int n,root,size,ans; 8 struct P{ 9 int l,r,sz,key,rd,re;//re为重复次数，key为加入权值 10 }t[1000005]; 11 void update(int k) 12 { 13 t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].re; 14 } 15 void left(int &k)//右旋 16 { 17 int y=t[k].r; 18 t[k].r=t[y].l; 19 t[y].l=k; 20 t[y].sz=t[k].sz; 21 update(k); 22 k=y; 23 } 24 void right(int &k)//左旋 25 { 26 int y=t[k].l; 27 t[k].l=t[y].r; 28 t[y].r=k; 29 t[y].sz=t[k].sz; 30 update(k); 31 k=y; 32 } 33 void init(int &k,int x)//加入操作 34 { 35 if(k==0) 36 { 37 size++; 38 k=size; 39 t[k].sz=1; 40 t[k].re=1; 41 t[k].key=x; 42 t[k].rd=rand(); 43 return; 44 } 45 t[k].sz++; 46 if(t[k].key==x) t[k].re++; 47 else{ 48 if(x>t[k].key) 49 { 50 init(t[k].r,x); 51 if(t[t[k].r].rd<t[k].rd) left(k);//这里和下面都是判断是不是满足堆的性质 52 } 53 if(x<t[k].key) 54 { 55 init(t[k].l,x); 56 if(t[t[k].l].rd<t[k].rd) right(k); 57 } 58 } 59 } 60 void del(int &k,int x) 61 { 62 if(k==0) return; 63 if(t[k].key==x) 64 { 65 if(t[k].re>1) 66 { 67 t[k].re--; 68 t[k].sz--; 69 return; 70 } 71 if(t[k].l*t[k].r==0) k=t[k].l+t[k].r;//k代表指针的移动，所以移动到了左或右儿子 72 else 73 { 74 if(t[t[k].l].rd<t[t[k].r].rd){ 75 right(k); 76 del(k,x); 77 } 78 else{ 79 left(k); 80 del(k,x); 81 } 82 } 83 } 84 else{ 85 if(x>t[k].key) 86 { 87 t[k].sz--; 88 del(t[k].r,x); 89 } 90 else{ 91 t[k].sz--; 92 del(t[k].l,x); 93 } 94 } 95 } 96 int rank1(int k,int x)//找x的排名 97 { 98 if(k==0) return 0; 99 if(t[k].key==x) return t[t[k].l].sz+1; 100 if(x>t[k].key) return t[t[k].l].sz+rank1(t[k].r,x)+t[k].re; 101 if(x<=t[k].key) return rank1(t[k].l,x); 102 } 103 int rank2(int k,int x)//找排名为x的数 104 { 105 if(k==0) return 0; 106 else if(x<=t[t[k].l].sz) return rank2(t[k].l,x); 107 else if(x>t[t[k].l].sz+t[k].re) return rank2(t[k].r,x-t[t[k].l].sz-t[k].re); 108 else return t[k].key; 109 } 110 void pre(int k,int x)//找前驱 111 { 112 if(k==0) return; 113 if(t[k].key<x) 114 { 115 ans=k; 116 pre(t[k].r,x); 117 } 118 else pre(t[k].l,x); 119 } 120 void nxt(int k,int x)//找后继 121 { 122 if(k==0) return; 123 if(t[k].key>x) 124 { 125 ans=k; 126 nxt(t[k].l,x); 127 } 128 else nxt(t[k].r,x); 129 } 130 int main() 131 { 132 srand(time(0)); 133 scanf("%d",&n); 134 for(int i=1;i<=n;i++) 135 { 136 int num,x; 137 scanf("%d%d",&num,&x); 138 if(num==1) init(root,x); 139 if(num==2) del(root,x); 140 if(num==3) printf("%d\n",rank1(root,x)); 141 if(num==4) printf("%d\n",rank2(root,x)); 142 if(num==5) 143 { 144 pre(root,x); 145 printf("%d\n",t[ans].key); 146 } 147 if(num==6) 148 { 149 nxt(root,x); 150 printf("%d\n",t[ans].key); 151 } 152 } 153 return 0; 154 }
模板题：https://www.luogu.org/problemnew/show/P3369
谢谢大家的观看。
如有不妥之处，请大家指出。
版权声明：本文为justin-cao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。