Splay(伸展树)

0.准备工作

在试图学习Splay之前,我们需要对一下内容加以理解:
1.神码是Dfs序
2.神码是二叉树的旋转
3.二叉树旋转之后为什么中序遍历不变(极其重要)
4.线段树区间操作是是什么原理


1.Splay 是神码

Splay是一种最优秀比较优秀的数据结构,它支持很多操作(几乎你想得到它就做得到),但是缺点就是常数较大。
Splay满足二叉搜索树的很多性质:

1.有序性:伸展树中的每一个节点的值都大于左儿子,小于右儿子
2.中序遍历不变性:伸展树无论经过怎样的旋转,中序遍历总是不变的,而且中序遍历肯定是升序遍历(或者你也可以让他降序)
3.自我调整性:简单说就是旋旋更健康:操作之后Splay()一下就可以维护树的健康度在logn左右(每次操作的复杂度),至于Splay是什么操作,待会会讲


2.如何实现一棵简单的Splay

首先,我们需要明确几个操作,以及它们的作用 。

请自行脑补这两个操作是如何进行的,然后我们再继续。

现在,我们需要将x节点向上转移,我们可以利用zig和zag操作。但是这也分多种情况。




所以以下就是将x节点旋转到根节点的操作

/*
wson为判断自己是父亲的哪个儿子的函数,,0左1右
*/
inline bool wson(int node){return tree[tree[node].fa].s[1]==node;}
inline void rot(int a)//有取反操作,可以很方便地执行zig或zag操作而不加判断
{
    int f=tree[a].fa,g=tree[f].fa,p=wson(a),q=wson(f);
    tree[f].s[p]=tree[a].s[!p],  tree[a].s[!p]=f,  tree[f].fa=a;//顺序很重要
    if(tree[f].s[p])tree[tree[f].s[p]].fa=f;
    if(tree[a].fa=g)tree[g].s[q]=a;
}
inline void splay(int node)
{
    while(tree[node].fa)
        if(!tree[tree[node].fa].fa)rot(node);//node是根节点的子节点
        else if(wson(node)!=wson(tree[node].fa))rot(node),rot(node);//链是弯的
        else rot(tree[node].fa),rot(node);//链是直的
    root=node;
}

好的,以上就是Splay最基本的操作之一,至于为什么要有这么多旋转法则,说白了就是为了让Splay树变健康。


3.Splay的插入操作

简单的想,我们需要找到一个节点,新建它的左儿子或者右儿子。至于如何找到那个节点,我们就要用到Splay的有序性。根节点一定比左儿子大,右儿子小。

/*
当前的节点是node,他的爸爸是fa.如果node==0,说明这个节点就是我们要找的节点,
我们就给fa新建一个子节点。
*/
//为了在新建节点的同时它父节点的儿子可以被更新,我们传入的是&node
void insrt(int x,int fa,int &node)
{
    if(!node){node=++cnt,tree[node].x=x,tree[node].fa=fa,splay(node);return;}
    if(x<tree[node].x)insrt(x,node,tree[node].s[0]);
    else if(x>tree[node].x)insrt(x,node,tree[node].s[1]);
}

4.Splay的前驱后继

过程类似插入操作,请自行脑补

 /*
同样,x是寻找前驱后继的值,node为节点
 */
int nxt(int x,int node)
{
    if(!node)return +1e8;
    if(tree[node].x==x){splay(node);return x;}
    if(tree[node].x>x)return min(nxt(x,tree[node].s[0]),tree[node].x);
    else return nxt(x,tree[node].s[1]);
}
int pre(int x,int node)
{
    if(!node)return -1e8;
    if(tree[node].x==x){splay(node);return x;}
    if(tree[node].x<x)return max(pre(x,tree[node].s[1]),tree[node].x);
    else return pre(x,tree[node].s[0]);
}

5.Splay节点的删除

我们需要将要删除的点Splay到根节点,然后删掉它。这时候会留下两颗孤独的子树,不过没关系,我们可以合并这两棵树。

/*
传入要删除的数(而不是节点编号),将该数删除
*/
void smax()
{
    int a=root;
    while(t[a].s[1])a=t[a].s[1];
    splay(a);
}
int find(int x,int a)
{
    while(a)
    {
        if(t[a].x==x)return a;
        else if(t[a].x<x)a=t[a].s[1];
        else a=t[a].s[0];
    }
    return a;
}
void del(int a)
{
    splay(find(a,root));
    int rs=t[root].s[1],ls=t[root].s[0];
    if(rs==0){t[root].s[0]=t[root].s[1]=t[root].f=0,root=ls,t[root].f=0;return;}
    if(ls==0){t[root].s[0]=t[root].s[1]=t[root].f=0,root=rs,t[root].f=0;return;}
    t[root].s[0]=t[root].s[1]=0;//先将根和子节点的联系断开
    t[rs].f=t[ls].f=0;
    root=ls;
    smax();//将左子树的最大值转到根
    t[root].s[1]=rs;//合并左右子树称为新的树
    t[rs].f=root;
}

综上所述,刚才的Splay可以完成插入、删除、修改、前驱、后继等操作。但是可以更多吗?


进阶Splay操作

真不清楚为什么,网上关于这类知识的介绍少之又少。我们能做的只是看着大神们的题解,一脸懵逼。出于各种考虑(其实就是因为我不会),这里就只放思路,不提供代码了。

1.Splay全局第k大

在刚才那棵简单Splay的节点中多保存一个值:子树大小。这样就可以根据子树大小来选择要查找的值在左子树还是右子树。如此方便。

2.序列在Splay中的保存

由于Splay需要满足有序性,所以我们可以很好的用它来储存一个序列。一个一维的序列经过Splay的保存,变身成为了拓扑性质完全不同的一棵树。但是这棵树又可以完美的还原原序列,并且可以更快速的完成对原序列的操作。这就是Splay称为序列之王的原因吧。
我们对Splay单调性的要求只要改为:x节点在原序列中的位置小于右儿子的位置大于左儿子的位置。我们就可以得到一棵beautiful的Splay。

3.Splay中子序列的提取

如果我们现在需要提取原序列[l,r]的区间,怎么做呢?
由于刚才我们讨论的Splay具有各种优良的性质,所以如果我们寻找区间[l,r],我们当然希望他们在一棵子树上。由于Splay的中序不变性,只要对它进行中序遍历就可以得到原序列。那么怎么做呢?
其实只需要把原序列第(l-1)位对应的节点Splay到根节点,再把节点(r+1)Splay到根节点的右儿子,那么节点(r+1)的左子树一定就是序列[l,r]。是不是很神奇又很自然。

4.Splay中序列的反转

这里就要用到线段树中常用的一中策略:懒惰标记。
如果我们要反转序列[l,r],我们就像 3.Splay的序列提取 里一样,将[l,r]变成一个子树,然后给子树的根节点打上懒惰标记,告诉它这棵树已经被反转了
然后就是标记下传,代码大概是这样的

/*
下传node的反转标记
*/
void pushdown(int node)
{
    if(tree[node].lazy)
    {
        swap(tree[node].son[0],tree[node].son[1]);
        if(tree[node].son[0])tree[tree[node].son[0]].lazy^=1;
        if(tree[node].son[1])tree[tree[node].son[1]].lazy^=1;
        tree[node].lazy=0;
    }
}

以及Splay的序列交换,序列求和等操作,序列加减等操作,已经可以模仿以上操作写出,这里不再继续扯淡。

分类: 文章