「OI」Splay

文艺平衡树 Splay,也叫伸展树、分裂树,是一种二叉排序树,它能快速完成插入、查找和删除操作。它是由丹尼尔·斯立特 Daniel Sleator 和 罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明的。

$\text{Splay}$ 是一种强大的数据结构。

简介

$\text{Splay}$ 的本质是一颗进化的二叉查找树。

但它与普通的二叉查找树相比,难度较大,所以常常有人说“去掉 S 我就会”(play),“去掉 p 我就会”(Slay,一款游戏)或者去掉 Sp 我就会(lay,指 躺着)。

下面介绍一下它的基本信息。

存储结构

root 表示整棵树的根节点编号。

编号为 $i$ 的节点存储:

  • 父亲节点的编号,用 fa[i] 表示;
  • 左右儿子节点的编号(没有一般设置成 $0$),用ch[i][0/1] 表示,ch[i][0] 表示左儿子,ch[i][1] 表示右儿子;
  • 当前节点的键值,用 val[i] 表示;
  • 以当前节点为根的子树大小,用 size[i] 表示;
  • 以当前节点内包含的元素个数,用 cnt[i] 表示。

基本操作

为了更加方便的操作

  1. $\operatorname{pushup}(x)$
    将编号为 $x$ 的节点的信息(主要指 size[x])更新。

    inline void pushup(reg int x){
        size[x]=sizez[ch[x][0]]+sz[ch[x][1]]+cnt[x];
        return;
    }
    
  2. $\operatorname{get}(x)$
    查询当前节点是该节点父亲节点的左儿子还是右儿子,左儿子返回 $0$(false),右儿子返回 $1$(true)。

    inline bool get(reg int x){
        return x==ch[fa[x]][1];
    }
    
  3. $\operatorname{clear}(x)$
    清空编号为 $x$ 的节点上储存的信息。

    inline void clear(reg int x){
        fa[x]=ch[x][0]=ch[x][1]=0;
        val[x]=size[x]=cnt[x]=0;
        return;
    }
    

核心操作

  1. $\operatorname{rotate}(x)$
    将 $x$ 旋转到原来父亲节点的位置上,同时不改变整棵树的中序遍历。
    下面我们考虑两种情况:
    $x$ 是父亲节点的左儿子。
    Splay-rotate-Z1.png
    $x$ 是父亲节点的右儿子。
    Splay-rotate-Z2.png
    于是可以写出代码。

    inline void rotate(reg int x){
        reg int f=fa[x],ff=fa[f];
        pushdown(x),pushdown(f); //这里的是魔改后的 Splay,所以与正常的有点不同
        bool w=get(x);
        ch[f][w]=ch[x][w^1];
        fa[ch[f][w]]=f;
        fa[f]=x;
        fa[x]=ff;
        ch[x][w^1]=f;
        if(ff)
            ch[ff][ch[ff][1]==f]=x;
        update(f); //这里的是魔改后的 Splay,所以与正常的有点不同
        return;
    }
    
  2. $\operatorname{splay}(x,\text{goal})$
    将 $x$ 转动到 $\text{goal}$ 的儿子位置($\text{goal}=0$ 表示把 $x$ 移到根节点的位置上)。

    inline void splay(reg int x,reg int goal){
        for(reg int qwq;(qwq=fa[x])!=goal;rotate(x))
            if(fa[qwq]!=goal)
                rotate(get(x)==get(qwq)?qwq:x);
        if(goal==0)
            root=x;
        return;
    }
    
  3. $\operatorname{insert}(x)$
    插入键值为 $x$ 的节点。
    插入操作是一个比较复杂的过程,具体步骤如下:

    • 如果树空了则直接插入根并退出。
    • 如果当前节点的权值等于 $x$ 则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行 $\operatorname{splay}$ 操作。
    • 否则按照二叉查找树的性质向下找,找到空节点就插入即可(当然别忘了 $\operatorname{splay}$ 操作哦)。
  4. $\operatorname{find}(x)$
    查找键值为 $x$ 的节点的编号。
    二分查找。

  5. $\operatorname{kth}(x)$
    求排名为 $x$ 的节点的权值。
    查找过程有点像权值线段树。

  6. $\operatorname{pre}(x)$
    查询 $x$ 的前驱。
    前驱定义为小于 $x$ 的最大的数,那么查询前驱可以转化为:将 $x$ 插入(此时 $x$ 已经在根的位置了),前驱即为 $x$ 的左子树中最右边的节点,最后将 $x$ 删除即可。

  7. $\operatorname{nxt}(x)$
    查询 $x$ 的后继。
    后继定义为大于 $x$ 的最小的数,那么查询后继可以转化为:将 $x$ 插入(此时 $x$ 已经在根的位置了),后继即为 $x$ 的右子树中最左边的节点,最后将 $x$ 删除即可。

  8. $\operatorname{del}(x)$
    删除 $x$。
    把 $x$ 转到根然后像二叉查找树一样删除。

注意事项

  1. 查询前驱或后继时左右子树必须存在,不然有的写法容易死循环,所以推荐先插入正负无穷作为哨兵节点防止出错。
  2. 不要随意地魔改 $\text{Splay}$,它太神奇了,改之前记得画画图。