「OI」平衡树

Splay

Splay 又称伸展树,顾名思义,这种平衡树是通过不断伸展来防止自身退化的。

基本思想

一颗二叉搜索树的中序遍历应当保持不变,也就是说,我们必须保证树中结点的中序遍历序列中键值单调递增。

根据我们的经验,只有先序遍历与中序遍历(或者后序遍历和中序遍历)同时给定时,我们才能唯一确定一颗二叉树。不难推出,同一个中序遍历会对应许多不同的二叉树,Splay 需要做的,就是通过不断的伸展操作(splay),对自身的树结构进行恒等变换,以减小深度。

存储结构

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

struct Node{
    int fa,ch[2]; //维护当前结点的父亲结点编号,儿子结点编号
    int siz,cnt; //维护子树大小与当前结点大小
    int sum,val; //存储子树权值和与当前结点权值
    #define fa(x) unit[(x)].fa
    #define ch(x) unit[(x)].ch
    #define siz(x) unit[(x)].siz
    #define cnt(x) unit[(x)].cnt
    #define sum(x) unit[(x)].sum
    #define val(x) unit[(x)].val
    #define lson(x) ch(x)[0]
    #define rson(x) ch(x)[1]
};
Node unit[MAXN]; //定义存储信息的数组

基本操作

下面先介绍基本操作,判断(get)、更新(pushup)。

基本操作 1 判断 get

该基本操作用于返回一个结点 $p$ 是否是其父亲结点的右儿子。

bool pushup(int p){
    return rson(fa(p))==p;
}

基本操作 2 更新 pushup

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

void pushup(int p){
    siz(p)=siz(lson(p))+siz(rson(p))+cnt(p);
    sum(p)=sum(lson(p))+sum(rson(p))+val(p);
    return;
}

核心操作

Splay 核心操作主要有两个:旋转(rotate)与伸展(splay),下面用图文来介绍两个操作。

核心操作 1 旋转 rotate

为了使 Splay 保持平衡而进行旋转操作,旋转的本质是将某个节点上移一个位置。

旋转需要保证 :

  1. 整棵 Splay 的中序遍历不变(不能破坏二叉查找树的性质);
  2. 受影响的节点维护的信息依然正确有效;
  3. root 必须指向旋转后的根节点;
  4. 在 Splay 中旋转分为两种:左旋和右旋。

我们可以用如下的示意图来表示旋转操作(来自 OI-wiki)。

平衡树
Splay 的旋转

写成代码是下面的样子。

void rotate(int p){
    int f=fa(p),ff=fa(f),w=get(p);
    ch(f)[w]=ch(p)[w^1];
    fa(ch(f)[w])=f;
    ch(p)[w^1]=f;
    fa(f)=p;
    fa(p)=ff;
    if(ff) ch(ff)[rson(ff)==f]=p;
    pushup(f),pushup(p);
    return;
}

核心操作 2 伸展 splay

splay 操作的目的就是为了减小树的深度和减少单点操作的复杂性。

splay 可以把一个结点通过不断旋转上升的某个结点儿子的位置上。

写成代码就是这样:

void splay(int p,int goal){
    for(int f;f=fa(p),f!=goal;rotate(p))
        if(fa(f)!=goal)
            rotate(get(p)==get(f)?f:p);
    pushup(p);
    if(!goal)
        rt=p;
    return;
}

实际应用

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

  • 普通平衡树
    • insert 在树上二分,找到对应的位置后新建结点(或者 cnt++ )即可;
    • del 在树上二分,找到对应的位置后删除结点(或者 cnt– )即可;
    • rnk 在树上二分后返回左树大小;
    • find 直接二分查找;
    • pre 在树上二分找到该结点后旋转到根然后找到左子树最大值即可;
    • suf 在树上二分找到该结点后旋转到根然后找到右子树最小值即可;
  • 文艺平衡树
    • reverse 把一段区间旋转到子树内,然后给子树打标记。

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

Pages: 1 2 3 4