记忆中的Splay

今天借着期末复习数据结构，又重新学习了一下splay,第二遍学感觉之前白书讲的完全框死了思维，其实splay是一个很好写也很好理解的数据结构.

• splay是一种排序二叉树，即左边节点的$val<=根的val<=右边节点的val$。
• 我们知道，一般的排序二叉树会退化，与treap给节点赋随机权值的方法不同，splay使用splay操作来进行平衡，使得摊还的平均复杂度为$O(logn)$，也就是说，每次操作完splay一下某个被操作的节点，不会使得复杂度变坏
• splay可以很方便的用在数列之中，将数列按照位置作为权值建立splay,中序遍历这棵splay即可得到这个数列。通过这种方式，splay可以完成几乎所有的线段树操作

下面稍微记一下splay操作如何实现
$splay(Node *u)$即把u节点转到根
总共分三种情况讨论一下

1. u的父亲是根节点。这时只要进行一次单旋即可。
2. u的父亲与u的祖父与u共线。这时候做法是先旋转u的祖父，再旋转u的父亲
3. u的父亲和u的祖父和u不共线。这时做法是先旋转u的父亲，再旋转u的祖父.

真正要记一下的就是共线与不共线两种情况，虽然对应的策略都是为了让二叉树显得更加平衡，但现在不能对此有直观的理解。但是代码还是很简单的。

void Splay(Node *u)
{
    while(u->p!=null)//rt->p=null
    {
        Node *p=u->p;
        int d=p->ch[1]==u;
        if(p->p==null)rotate(p,d);
        else
        {
            Node *pp=p->p;
            int d2=pp->ch[1]==p;
            if(d2==d)
            {
                rotate(pp,d2);
                rotate(p,d);
            }
            else
            {
                rotate(p,d);
                rotate(pp,d2);
            }
        }
    }
    u->push_up();
    rt=u;
}

由于u节点一直在旋转，所以中间过程可以对其不进行push_up()操作而只在最后转到根了再对其进行push_up()操作.再给出rotate和Node节点的代码.

struct Node
{
    int sz,val;
    Node *ch[2],*p;
    void push_up()
    {
        sz=ch[0]->sz+ch[1]->sz+1;
    }
    void setc(int d,Node *v)
    {
        ch[d]=v;v->p=this;
    }
};
void rotate(Node *u,int d)
{

    Node *v=u->ch[d];
    u->p->setc(u->p->ch[1]==u,v);
    u->setc(d,v->ch[d^1]);
    u->push_up();
    v->setc(d^1,u);
}

接着就是考虑插入和删除节点。
插入节点比较容易，一般就是找到权值合适的位置，然后只要修改那个节点就可以了。为了让之后操作的复杂度更平均些，新插入的节点我们一般将其旋转到根。

void insert(int x)//插入一个权值为x的节点
{
    Node*u=rt;
    int d=x>u-val;
    while(u->ch[d]!=null)
    {
        u=u->ch[d];
        d=x>u->val;
    }
    Node *t=&nd[cnt++];//nd为内存池，cnt为使用的内存
    t->init(x);//对新节点进行初始化
    u->setc(d,t);
    splay(t);
}

与treap稍微有些不同，splay的删除操作更加直观，简单。因为spaly操作并不会为复杂度带来负担，为什么不把节点放到根上去进行操作呢？删除就是先找到待删除的点，将其旋转到根，然后找到这个点的后继，再将后继旋转到根，这时候注意到待删除的点必然没有右子树，因此简单的把他的左子树设成根的左儿子就可以了。

void Delete(Node*u)
{
    splay(u);
    if(u->ch[0]==null)setrt(u->ch[1]);
    else if(u->ch[1]==null)setrt(u->ch[0]);
    else
    {
        Node *v=u->ch[1];
        while(v->ch[0]!=null)v=v->ch[0];
        splay(v);
        v->setc(0,u->ch[0]);
    }
}

至此，插入、删除就都实现了。其实仔细思考一下，假如在splay的同时维护lazy标记，splay是可以进行区间操作的。具体要注意的之后再补。