平衡树（二）—

平衡树（二）——Treap

前言
简介
定义
一些操作
- 更新
- Treap rotate (旋转)

前言

在上文中说道，(BST) （二叉搜索树）是个好东西，但是遇见某些有序的数据，那么树也就会退化成一条链，所以我们说普通的 (BST) 是不平衡的

简介

关于 (Treap) ((BST + Heap)) 是一种简单的平衡树，相比于 (BST) ，它的每个节点有权值外，还有一个随机值，我们可以按照随机值维护队的形状，因此 (Treap) 的期望深度就成了 (O(log n))

下面代码直接复制的蓝书上的，~~主要是懒得打了 = =~~

定义

(t[x].lc) (x) 的左儿子
(t[x].rc) (x) 的右儿子
(t[x].key) (x) 节点的权值
(t[x].r) (x) 节点的随机值
(t[x].cnt) (x) 节点重复元素的个数
(t[x].siz) 以 (x) 为根的子树的大小

struct Tree{
   int ls, rs, key, r, cnt, siz;
   #define ls(x) t[x].ls
   #define rs(x) t[x].rs
   #define v(x) t[x].key
   #define r(x) t[x].r
   #define cnt(x) t[x].cnt
   #define siz(x) t[x].siz
} t[N]

一些操作

更新

void push_up(const int &p){
   siz(p) = siz(lc(p)) + siz(rs(p)) + cnt(p);
}

Treap rotate (旋转)

Zig（左旋）

左旋之后，就成了下面这个样了 = =

不难发现旋转之后它依然满足 (BST) 的性质

所以我们可以利用这个操作来满足每个点的随机值按照某个顺序排序

void Zig(int &p){
   int y = rs(p);
   rs(p) = ls(y);
   ls(y) = p;
   push_up(p), push_up(y);//更新权值
   p = y;
}

一步步来

对下面的这个图进行左旋操作

(y = rs(p)) 先把新根存下来

(rs(p) = ls(y))

让 (y) 的左儿子成为 (p) 的右儿子

       A(p)                         
       /               
      B   D   C(y)               
                             
                E

(ls(y) = p)

让 (y) 的左儿子变为 (p) （让旧根接在新根上）

        C(y)
       / 
   (p)A   E
     /    
    B   D

完事 ! ! !

Zag (右旋)

思路和左旋一个样

直接上代码 = =

void Zag(int &p){
   int y = ls(p);
   ls(p) = rs(y);
   rs(y) = p;
   push_up(p), push_up(y);
   p = y;
}

Insert (插入)

首先按照权值插入，方法和 (BST) 一样（如果该点权值比当前节点大，就向右插，否则就向左插，如果为空节点就新建一个）

这样插入树的优先级可能就乱了，所以还要进行旋转操作，来维护树的优先级

插入后，如果左孩子的随机值小于当前节点的随机值，对当前节点进行右旋
插入后，如果右孩子的随机值小于当前节点的随机值，对当前节点进行左旋

直接上代码，图就不画了 (偷个懒 = =)

void Insert(int &p, const int &key) {
   if(!p){
     p = ++pool, v(p) = key, r(p) = rand();
     cnt(p) = siz(p) = 1, ls(p) = rs(p) = 0;
     return ;
   }
   else ++siz(p);
   if(v(p) == key) ++cnt(p);
   else if(key > v(p)){
       Insert(ls(p), key);
       if(r(ls(p)) < r(p)) Zig(p);//第一种情况
   }
   else {
       Insert(rs(p), key);
       if(r(rs(p)) < r(p)) Zag(p);//第二种情况
   }
}

Delete(删除)

对于叶子节点，可以直接删除
对于链上的节点，可以删除这个节点之后，让它的儿子节点直接继承这个节点
一个节点有两个非空子节点，先对它进行旋转，让它成为上面的两种情况，然后就可以直接删除删除它了，如果结点的左子节点的随机值小于右节点的随机值，右旋该节点，否则就左旋该节点，直到它成为上面的两种情况然后直接删除

void Delete(int &p, const int &key) {
  if(v(p) == key) {
    if(cnt(p) > 1) --cnt(p), --siz(p);//重复的节点
    else if(!ls(p) || !rs(p)) p = ls(p) + rs(p);//前两种情况
    else if(p(ls(p)) < p(rs(p))) Zig(p), Delete(p, key);
    else Zag(p), Delete(p, key);
  }
  --siz(p);
  if(key < v(p)) Delete(ls(p), key);
  else Delete(rs(p), key);
}

pre(查前驱)

给定一个元素，求出平衡树中不大于该元素的最大值

初始化为最优节点为空节点
从根节点依次访问，如果当前节点小于等于该元素，更新最优节点，然后访问该点的右结点；否则直接访问左节点

void query_pre(const int &key){
   int x = root, res = -inf;
   while(x) {
     if(v(x) <= key) res = v(x), x = rs(x);
     else x = ls(x);
   }
   return res;
}

suc (查后继)

给定一个元素，求出平衡树中不小于该元素的最小值

和上面完全一个样啦

query_suc(const int &key){
  int x = root, res = inf;
  while(x) {
    if(v(x) >= key) res = v(x), x = ls(x);
    else x = rs(x);
  }
  return res;
}

rank (求元素排名)

求出一个元素在树中是第几大滴（也就是树中小于该元素的节点有多少个）

从根节点开始找
所求的元素等于该节点，直接统计答案
如果所求元素小于该节点，向左子树中查询
如果所求的元素大于该节点，更新答案，然后向右子树查找要求的元素的排名

int query_rank(const int &key) {
    int x = root, res = 0;
    while(x) {
      if (key == v(x)) return res + siz(ls(x)) + 1;
      if (key < v(x)) x = ls(x);
      else res += siz(ls(x)) + cnt(x), x = rs(x);
    }
    return res;
}

Kth (求排名第 k 的元素)

从根节点开始找
若 (siz(ls(x)) + 1 leq k leq siz(ls(x)) + cnt(x)) (x) 就是答案
若 (k < siz(ls(x)) + 1) 继续向左子树查找排名第 (k) 的元素
(k > siz(ls(x)) + cnt(x)) 向右子树查找排名第 (k - (siz(ls(x)) + cnt(x))) 的元素

int query_Kth(int k){
    int x = root;
    while(x) {
       if(siz(ls(x)) < k && siz(ls(x)) + cnt(x) >= k) return v(x);
       if(siz(ls(x)) >= k) x = ls(x);
       else k -= siz(ls(x)) + cnt(x), x = rs(x);
    }
}

(finish)