平衡树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

谢谢大家的观看。

如有不妥之处，请大家指出。