什么时候左旋右旋

Treap如何写 - 图1

当对树的形态进行操作的时候 才会进行zig/zag 各种查询操作均用不上

  1. 插入的时候判断一下新增的节点的方向上 是否需要maintain
  2. 删除的时候通过旋转 把要删除的节点旋转至 叶子 然后删除
  3. 右旋先对右儿子进行pushup 再对父亲做
  4. 新增节点 删除节点 以及左旋右旋后 pushup

常见issues

见代码注释

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<ctime>
  7. using namespace std;
  8. // #define int long long 
  9. const int maxn = 1e6 + 10;
  10. const int INF = 0x7fffffff;
  11. struct node{
  12.   int l, r;
  13.   int val, dat;
  14.   int cnt, siz;
  15. }treap[maxn << 2];
  16. int tot, root , n;
  17. int New(int val){
  18.   treap[++tot].val = val;
  19.   treap[tot].dat = rand();
  20.   treap[tot].cnt = treap[tot].siz = 1;
  21.   return tot;
  22. }
  23. void pushup(int x){
  24.   treap[x].siz = treap[treap[x].l].siz + treap[treap[x].r].siz + treap[x].cnt;
  25. }
  26. void build(){
  27.   /*
  28.   在找前驱和后继的时候防止找到空节点
  29.   */
  30.   New(-INF); 
  31.   New(INF);
  32.   root = 1;
  33.   treap[1].r = 2;
  34.   pushup(root);
  35. }
  36. /*
  37. 右旋， 本来的父亲节点成为了自己左儿子的右儿子
  39. */
  40. void zig(int &x){ 
  41.   int y = treap[x].l;
  42.   treap[x].l = treap[y].r;  //原本父亲节点的左儿子变成了  他左儿子的右儿子
  43.   treap[y].r = x; // 左儿子的右儿子 变成了原本的父亲节点
  44.   x = y;
  45.   pushup(treap[x].r);
  46.   pushup(x);
  48. }
  49. /*
  50. 左旋， 本来的父亲节点成为了自己右儿子的左儿子
  51. */
  52. void zag(int &x){
  53.   int y = treap[x].r;
  54.   treap[x].r = treap[y].l;
  55.   treap[y].l = x;
  56.   x = y;
  57.   pushup(treap[x].l);
  58.   pushup(x);
  60. }
  61. void insert(int &x, int val){
  62.   if(x == 0){
  63.     x = New(val);
  64.     return;
  65.   }
  66.   if(val == treap[x].val){  //已经有的值增加计数即可
  67.     treap[x].cnt++;
  68.     pushup(x);
  69.     return;
  70.   }
  71.   if(val < treap[x].val){
  72.     insert(treap[x].l, val);
  73.     if(treap[x].dat < treap[treap[x].l].dat){
  74.       zig(x);
  75.     }
  76.   } else{
  77.     insert(treap[x].r, val);
  78.     if(treap[x].dat < treap[treap[x].r].dat){
  79.       zag(x);
  80.     }
  81.   }
  82.   pushup(x);
  83. }
  84. int getPre(int val){
  85.   int ans = 1;
  86.   int x = root;
  87.   while(x){
  88.     if(val == treap[x].val){
  89.       if(treap[x].l > 0){
  90.         x = treap[x].l;
  91.         while(treap[x].r > 0) x = treap[x].r;  //往左子树中的右边一直找
  92.         ans = x;
  93.       }
  94.       break;
  95.     }
  96.     if(treap[x].val < val&&treap[x].val > treap[ans].val) ans = x; 
  97.       //可以作为前驱的答案 比当前答案更优
  98.     x = val < treap[x].val? treap[x].l : treap[x].r;
  99.   }
  100.   return treap[ans].val;
  101. }
  102. int getNxt(int val){
  103.   int ans = 2;
  104.   int x = root;
  105.   while(x){
  106.     if(val == treap[x].val){
  107.       if(treap[x].r > 0){
  108.         x = treap[x].r;
  109.         while(treap[x].l > 0) x = treap[x].l;
  110.         ans = x;
  111.       }
  112.       break;
  113.     }
  114.     if(treap[x].val > val&&treap[x].val < treap[ans].val) ans = x;
  115.     x = val < treap[x].val? treap[x].l:treap[x].r;
  116.   }
  117.   return treap[ans].val;
  118. }
  119. void remove(int &x, int val){
  120.   if(x == 0) return;
  121.   if(val == treap[x].val){
  122.     if(treap[x].cnt > 1){
  123.       treap[x].cnt--;
  124.       pushup(x);
  125.       return;
  126.     }
  127.     if(treap[x].l || treap[x].r){
  128.       if(treap[x].r == 0|| treap[treap[x].l].dat > treap[treap[x].r].dat){
  129.         zig(x);
  130.         remove(treap[x].r, val);
  131.       } else{
  132.         zag(x);
  133.         remove(treap[x].l, val);
  134.       }
  135.       pushup(x);
  136.     } else{
  137.       x = 0;
  138.     }
  139.     return;
  140.   }
  141.   val < treap[x].val? remove(treap[x].l, val):remove(treap[x].r, val);
  142.   pushup(x);
  143. }
  144. int getRankByVal(int x, int val){
  145.   if(x == 0) return 0;
  146.   if(val == treap[x].val){
  147.     return treap[treap[x].l].siz + 1;  // 比他小的数+1  即得到排名
  148.   }
  149.   if(val < treap[x].val){
  150.     return getRankByVal(treap[x].l, val);  //  比当前值还要小 继续往左子树找
  151.   } else{
  152.     /*
  153.     左边的小的 全部算上 当前节点也比你要找的值小 有多少副本数全部算上
  154.     */
  155.     return treap[treap[x].l].siz + getRankByVal(treap[x].r, val) + treap[x].cnt; 
  156.   }
  157. }
  158. int getValByRank(int x, int rank){
  160.   if(x == 0) return INF;
  161.   if(treap[treap[x].l].siz >= rank){
  162.     //比你小的数  还有很多 还要继续往左边找
  163.     return getValByRank(treap[x].l, rank);
  164.   } else if((treap[treap[x].l].siz + treap[x].cnt) >= rank){
  165.     //本身的副本数刚好覆盖掉了  就是当前的值
  166.     return treap[x].val;
  167.   } else{
  168.     //继续往比当前值大的区域寻找    要找的名词减去当前点以及它左子树的贡献
  169.     return getValByRank(treap[x].r, rank - treap[treap[x].l].siz - treap[x].cnt);
  170.   }
  171. }
  172. int main()
  173. {
  174.   // freopen("out.txt", "w", stdout);
  175.     build();
  176.     int op, x;
  177.     scanf("%d", &n);
  178.     for(int i = 0; i < n; ++i)
  179.     {
  180.         scanf("%d%d", &op, &x);
  181.         switch(op)
  182.         {
  183.             case 1:        //插入
  184.                 insert(root, x);
  185.                 break;
  186.             case 2:        //删除
  187.                 remove(root, x);
  188.                 break;
  189.             case 3:        //按值查询 排名
  190.                 printf("%d\n", getRankByVal(root, x) - 1);
  191.                 break;
  192.             case 4:        //按排名查询值
  193.                 printf("%d\n", getValByRank(root, x + 1));
  194.                 break;
  195.             case 5:        //前驱
  196.                 printf("%d\n", getPre(x));
  197.                 break;
  198.             case 6:        //后继
  199.                 printf("%d\n", getNxt(x));
  200.                 break;
  201.         }
  202.     }
  203.     return 0;
  204. }