「OI」平衡树

FHQ-Treap

FHQ-Treap 是 Treap 的一种变种,它可以利用堆的性质来保证自身的深度为 $\Theta(\log_2n)$,进而防止自身退化为链。

基本思想

FHQ-Treap 的思路与 Treap 基本相同。堆是一种优雅的数据结构,而二叉堆是一种特殊而又简单的堆结构。二叉堆在大多时候都是一颗完全二叉树,也就是说,对于一个节点数量为 $n$ 的堆,其深度为 $\Theta(\log_2n)$ 级别。

Treap 利用这种堆的性质,考虑根据堆的理论进行随机权值合并,这样使得整颗平衡树的深度为 $\Theta(\log_2n)$。

而 FHQ-Treap 是 Treap 的进阶版本。它删除了普通 Treap 的旋转操作,避免了 Treap 维护过程中大量的父子关系变化。它使用了两种新操作,分裂(split)与合并(merge)。

存储结构

FHQ-Treap 的基本存储结构是结点,也就是是说,我们所有的信息都被存储在结点上。

struct Node{
    int ch[2];
    int siz;
    int val;
    #define ch(x) unit[(x)].ch
    #define siz(x) unit[(x)].siz
    #define val(x) unit[(x)].val
    #define lson(x) ch(x)[0]
    #define rson(x) ch(x)[1]
};
Node unit[MAXN];

基本操作

FHQ-Treap 的基本操作只有两个,就是新建(new)与更新(pushup)。

基本操作 1 新建 new

该基本操作用于新建一个权值为 $v$ 的节点。

int New(int v){
    int p=++tot;
    lson(p)=rson(p)=0;
    siz(p)=1;
    val(p)=v;
    return p;
}

基本操作 2 更新 pushup

该基本操作用于更新结点 $p$ 存储的信息。

void pushup(int p){
    siz(p)=siz(lson(p))+siz(rson(p))+1;
    return;
}

核心操作

FHQ-Treap 主要有两个核心操作,分裂(split)和合并(merge)。

核心操作 1 分裂 split

分裂操作主要有两种,按子树大小分裂与按键值分裂。

按照子树大小分裂时,我们考虑当前节点的左右儿子,如果左儿子的大小 $+1$ 小于等于目标值,则根与左儿子在同一颗树中,我们递归分裂右儿子;否则我们递归分裂左儿子。

写成代码是这样:

void split(int p,nt k,int &x,int &y){
    if(!p){
        x=y=0;
        return;
    }
    if(siz(lson(p))<k){ //等价于 siz(lson(p))+1<=k
        x=p;
        split(rson(x),k-siz(lson(p))-1,rson(x),y);
        pushup(x);
    }
    else{
        y=p;
        split(lson(y),k,x,lson(y));
        pushup(y);
    }
    return;
}

按键值分裂时,我们同理进行递归考虑,写成代码如下:

void split(int p,int v,int &x,int &y){
    if(!p){
        x=y=0;
        return;
    }
    if(val(p)<=v){
        x=p;
        split(rson(x),v,rson(x),y);
        pushup(x);
    }
    else{
        y=p;
        split(lson(y),v,x,lson(y));
        pushup(y);
    }
    return;
}

核心操作 2 合并 merge

合并操作 merge 的实际用途是,将两颗树连起来,并且使得原树的中序遍历是正好连起来,不交叉。

合并操作则比较简单,我们按照中序遍历的有序性进行合并即可。由于 FHQ-Treap 的高度自由,它的树结构事实上是依靠我们自己维护的。换句话说,树的结构由执行 merge 的顺序决定,而 merge 函数的实现与权值大小无关。

int merge(int x,int y){
    if(!x||!y)
        return x|y;
    if(rand()%(siz(x)+siz(y))<siz(x)){
        rson(x)=merge(rson(x),y);
        pushup(x);
        return x;
    }
    else{
        lson(y)=merge(x,lson(y));
        pushup(y);
        return y;
    }
}

附加操作

FHQ-Treap 的附加操作与绝大多数平衡树类似,就是打一点 lazy-tag。

常见的有子树加(add)、子树乘(mul)、子树翻转(rev)等操作。

具体的思想,就是把对应区间分裂(split)成三部分,其中中间是我们需要修改的部分,打上修改标记,后面再重新合并(merge)即可。

//rt 是当前树的根

static int rt1,mid,rt2;

split(rt,*,rt1,rt2); //先把右边部分分裂出来,记作 rt2
split(rt1,*,rt1,mid); //再把左边与中间分开,为 rt1,mid

***(mid); //对中间进行修改

rt=merge(merge(rt1,mid),rt2); //重新合并为一颗树

实际应用

下面我们按照惯例解决一下模板题。

  • 普通平衡树
    • insert 按照键值进行分裂(split),然后新建(new)节点,最后合并(merge);
    • del 按照键值分裂(split)三部分,如果中间这部分删除后消失,那么不合并(merge),否则去除一个之后合并(merge);
    • rnk 键值分裂(split)后返回左树大小;
    • find 直接二分查找;
    • pre 键值分裂(split)后返回左子树 max;
    • suf 分裂(split)后返回右子树 min;
  • 文艺平衡树
    • reverse 对应按照子树大小把树分裂(split)成为三个区间,中间区间翻转后再合并(merge)即可。

快速解决了模板题目,FHQ-Treap 实在是太棒了。

Pages: 1 2 3 4