树堆treap

admin

普通BST在使用过程中可能会被卡成一条链，那就和数组没有太大的差别了，为了避免这种情况，采用给每个节点加上随机权重rd的方法，有点类似于快速排序的时候随机选择a(l)-a(r) 中的元素来划分，而不是固定采用a(l)来自作为的分割元素。我们把这个BST排成根节点权值小，子节点权值大，当然还是左子树val小，右子树val大。
那么在随机化的情况下这棵树一般不会退化得很离谱，但是在插入删除的时候带来了一个新的麻烦，一般情况下val合适的插入位置不见得能满足rd
也就是说当a(l).val<a(rt).val a(r).val>a(rt).val时不见得能满足 a(l).rd>a(rt).val a(r).rd>a(rt).val，比如图上的，假设以前1234678节点都已经满足了条件，新插入了节点x(val=5,rd=15)，按照普通BST的规定，他应该作为4节点的右子树，但是，他的rd15小于4节点的rd25，怎么办呢？




我们旋转一下这个红圈里面的树，4是原来的根，现在变成5,4变成5的左子树，对于BST来说没有影响，但是rd却满足了堆的性质



当然，5放在2的下面也是不符合堆的性质，不要紧，我们继续调，好像可以递归哦！

admin

插入进树前面学过，是比较简单的，那么treap的重点就是如何旋转。简单起见我们规定两种旋转，一个是LR，把rd比较小的点往上移动，（上面例子里面的5挪到4的位置然后在挪到2的位置就是），另外一个是RR，把rd较大的点往下移动，和它是相反的。

admin

RR和LR的代码如下，中间加上了pushup()函数，这个pushup和线段树里面是一样的，树根变动了，那么sz等信息也会改变。

1. void pushup(int rt)   ///类似线段树往上调整
   
2. {
   
3.         int l=a[rt].ls, r=a[rt].rs;
   
4.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
   
5. }
   
6. 
   
7. void RR(int &rt) /// 把x的左儿子旋上来当根
   
8. {
   
9.         int l=a[rt].ls;
   
10.         a[rt].ls=a[l].rs;///左儿子的右儿子变成了我的左儿子
    
11.         a[l].rs=rt;///自己变成了左儿子的右儿子
    
12.         pushup(rt),        pushup(l),rt=l;///挂上
    
13. }
    
14. void LR(int &rt)/// 把x的右儿子旋上来当根
    
15. {
    
16.         int r=a[rt].rs;
    
17.         a[rt].rs=a[r].ls;///右儿子的左儿子变成了我的右儿子
    
18.         a[r].ls=rt;///自己变成了右儿子的左儿子
    
19.         pushup(rt),pushup(r),rt=r;///挂上
    
20. }

复制代码

admin

那么剩下的就和普通BST差不多了，在每次插入和删除的时候要检查rd，进行适当的调整，先看看插入的过程：

1. void Ins(int &rt, int x)   /// 在rt子树中插入x
   
2. {
   
3.         if(rt==0)   ///空树就新建
   
4.                 {
   
5.                         rt=++tot;
   
6.                         a[rt].val=x;
   
7.                         a[rt].sz=a[rt].cnt=1;
   
8.                         a[rt].rd=rand();  ///随机值
   
9.                 }
   
10.         else
    
11.                 {
    
12.                         a[rt].sz++; /// 新增了
    
13.                         if(a[rt].val==x) a[rt].cnt++;
    
14.                         else
    
15.                                 {
    
16.                                         if(a[rt].val<x)
    
17.                                                 {
    
18.                                                         ///cout<<'R';
    
19.                                                         Ins(a[rt].rs,x);
    
20.                                                         if(a[rt].rd>a[a[rt].rs].rd) LR(rt); ///.rd调整
    
21.                                                 }
    
22.                                         else if(a[rt].val>x)
    
23.                                                 {
    
24.                                                         ///cout<<'L';
    
25.                                                         Ins(a[rt].ls, x);
    
26.                                                         if(a[rt].rd>a[a[rt].ls].rd) RR(rt);///.rd调整
    
27.                                                 }
    
28. 
    
29.                                 }
    
30.                 }
    
31. }

复制代码

admin

再看看删除的过程，和标准BST相比，有哪些区别?

1. void Del(int &rt,int x)
   
2. {
   
3.         if(rt>0)
   
4.                 if(a[rt].val==x)
   
5.                         {
   
6.                                 if(a[rt].cnt>1)        a[rt].cnt--, a[rt].sz--;    //有相同的就直接cnt--
   
7.                                 else
   
8.                                         {
   
9.                                                 if (a[rt].ls==0) rt=a[rt].rs;  ///右子树接上来
   
10.                                                 else if (a[rt].rs==0) rt=a[rt].ls;///左子树接上来
    
11.                                                 else
    
12.                                                         {
    
13.                                                                 if (a[a[rt].ls].rd>a[a[rt].rs].rd) RR(rt);else LR(rt); ///rd调整  
    
14.                                                                 Del(rt,x);
    
15.                                                         }
    
16.                                         }
    
17.                         }
    
18.                 else
    
19.                         {
    
20.                                 a[rt].sz--;
    
21.                                 if (a[rt].val<x) Del(a[rt].rs, x);
    
22.                                 else Del(a[rt].ls, x);
    
23.                         }
    
24. }

复制代码

由于已经有了旋转的操作，所以我们大可以找到后。把要删除的那个节点的某个rd较小的儿子转上来当根，把他往下压。直到他没左右儿子为止。然后直接删除。