华师一附中OI组

标题: 树堆treap [打印本页]
作者: admin    时间: 2020-3-29 17:31
标题: 树堆treap
普通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    时间: 2020-3-29 18:26
插入进树前面学过，是比较简单的，那么treap的重点就是如何旋转。简单起见我们规定两种旋转，一个是LR，把rd比较小的点往上移动，（上面例子里面的5挪到4的位置然后在挪到2的位置就是），另外一个是RR，把rd较大的点往下移动，和它是相反的。



作者: admin    时间: 2020-3-29 18:29
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. }

  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    时间: 2020-3-29 18:36
那么剩下的就和普通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.                                                 }

  29.                                 }
  30.                 }
  31. }
复制代码
作者: admin    时间: 2020-3-29 18:44
再看看删除的过程，和标准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较小的儿子转上来当根，把他往下压。直到他没左右儿子为止。然后直接删除。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2