Splay讲解

2018/04/24 16:04
阅读数 35

Splay讲解

  Splay是平衡树的一种,是一种二叉搜索树,我们先讲解一下它的核心部分。

  Splay的核心部分就是splay,可能有些人会说什么鬼?这样讲解是不是太不认真了?两个字回答:不是。第一个Splay是算法名称,而第二个splay是一个函数,如果说是一个函数,还不如说是两个函数,splay和rotate。下面开始讲解:

rotate

  Splay最重要的部分就是两种基本旋转:zig,zag。本人在此理解的zig是左旋而zag是右旋。学过Treap的人可能会想到Treap的左右两旋,那两个旋转和这两个旋转是不一样的,Treap的旋转是讲自己的儿子旋上来,而Splay的旋转是将自己旋到父亲上去,两者的本质是不同的。

  首先先讲解zag:我们要旋转的时候,一定会用到当前节点的父亲,所以我们需要存一个父亲数组,来记录当前节点的父亲是谁。当然我们还需要记录儿子是谁——左右两个儿子。现在就可以开始旋转了,如图(将B号节点旋到他的父亲A号节点的上方),是不是和treap的右旋十分相像?就是treap的右旋是在A号节点完成的,而zag是在B号节点完成的。


void zag(int p)
{
    int tmp=fa[p],tmp2=fa[tmp];
    lson[tmp]=rson[p],fa[rson[p]]=tmp;
    rson[p]=tmp,fa[tmp]=p,fa[p]=tmp2;
    if(lson[tmp2]==tmp) lson[tmp2]=p;
    else rson[tmp2]=p;
    update(tmp),update(p);
}

  同理,zig就十分简单了,如图(将A号节点旋到他的父亲B号节点的上方)。

void zig(int p)
{
    int tmp=fa[p],tmp2=fa[tmp];
    rson[tmp]=lson[p],fa[lson[p]]=tmp;
    lson[p]=tmp,fa[tmp]=p,fa[p]=tmp2;
    if(lson[tmp2]==tmp) lson[tmp2]=p;
    else rson[tmp2]=p;
    update(tmp),update(p);
}

  这就是zig和zag两种旋转,但我们大家仔细思考一下,这两个旋转的代码基本一致,是不是可以合成一个函数?答案是可以。我们开一个数组,为son[p][2],这个数组的含义就是p号节点的左右两个儿子,son[p][0]表示p号节点的左儿子,而son[p][1]表示p号节点的右儿子。这样我们进行旋转就十分方便了,我们进行一次check看我要左旋还是右旋就可以了,我们可以写一个chek函数返回值就是0和1,这样的话直接把返回值放在第二维就好了。

bool check(int p)
{
    return p==son[fp][1];
}
void rotate(int p)
{
    int tmp=fp;
    int tmp2=ftp;
    int tmp3;
    check(p)?tmp3=1:tmp3=0;
    fa[son[tmp][tmp3]=son[p][tmp3^1]]=tmp;
    fa[p]=tmp2;
    if(tmp2) son[tmp2][check(tmp)]=p;
    fa[son[p][tmp3^1]=tmp]=p;
    update(tmp),update(p);
}

  旋转rotate讲解完毕,有问题可以发评论,我会解答。下面讲解splay,splay的功能就是将当前节点旋转到顶点,实际上就是一个循环。旋转一共有六种组合,下面我会逐个解释。

splay

  第一种:当前节点直接就是根节点左儿子,直接zag就好啦。同理第二种:当前节点是根节点的右儿子,直接zig。

  第三种(如左一图):我们需要先将当前节点的父亲旋转上去,再将自己旋转上去,就是先zag(父亲),再zag(自己)。同理第四种(如左二图):先zig(父亲),再zig(自己)。

  第五种(入右二图):我们需要先将当前节点旋转上去,再讲他的父亲旋转上去,就是先zig(自己),再zag(父亲)。同理第六种(如右一图):先zag(自己),再zig(父亲)。

  每次旋转的时候我们需要check一下具体实现比较简单。下面的代码是写的将当前节点旋转到指定的节点也就是所写(order),这样写的原因下面会说。

void splay(int p,int &order)
{
    int tmp2=fa[order];
    for(int tmp;(tmp=fp)!=tmp2;rotate(p))
        if(ftp!=tmp2)
            rotate(check(p)==check(tmp)?tmp:p);
  order=p;
}

  splay也讲解完毕,不会的也可以发评论问我。

区间操作

  最后讲解一下splay比treap多出的操作,就是区间操作。这也就是为什么像上面那样书写代码,我们如果要对权值为[x,y]的这个区间进行操作,我们可以查找到x-1这个值的节点,将其旋转到root,再找到y+1这个值的节点,将其旋转到root的右儿子上。旋转之后,根据BST的性质,我们可以知道root的右儿子的左子树就是我们要的区间,直接进行操作就好啦,是不是很简单?

  问题依旧可以发到评论之中。

展开阅读全文
zig
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部