Splay平衡树

Splay平衡树

基于 Splay 伸展操作维持平衡的二叉树，不断将某个节点旋转到根节点，可以在均摊 $O(\log n)$ 的时间内完成插入查找和删除操作

节点的定义：

struct node{
    int s[2];//左儿子0，右儿子1
    int v;//节点的权值
    int cnt;//权值的次数
    int p;//节点的父亲
    int siz;//以节点为根的子树大小
    void init(int x,int y){//初始化
        v=x,p=y;
        cnt=siz=1;
    }
};

其他数组的定义：

node tr[N];
int root,idx;//根节点以及节点序号

Rotate 旋转操作，根据树形态的不同，分为左旋和右旋

将传入的节点 $x$ 进行旋转，如果 $x$ 是他父亲的左儿子，那么进行右旋，如果 $x$ 是他父亲的右儿子，那么进行左旋

定义 $y$ 表示 $x$ 的父亲，$z$ 表示 $y$ 的父亲

需要维护平衡二叉树的性质，即一个节点的左子树上的所有权值都小于该节点的权值，右子树上的所有权值都大于该节点的权值

右旋：

• 将 $x$ 的右儿子重新绑定在 $y$ 的左儿子上
• 把 $x$ 旋转为 $y$ 的父亲，即把 $y$ 绑定在 $x$ 的右儿子上
• 最后将 $x$ 绑定在原来 $y$ 对应 $z$ 的某个儿子的位置上

同样左旋的操作可以类比

void rotate(int x){
    int y=tr.p,z=tr[y].p;
    bool r=tr[y].s[1]==x;//判断左旋还是右旋
    //x是y的右儿子时r=1，进行左旋操作。x是y的左儿子时r=0，进行右旋操作
    tr[y].s[r]=tr.s[r^1];
    tr[tr.s[r^1]].p=y;
    //绑定x的某个儿子到y上
    tr.s[r^1]=y;
    tr[y].p=x;
    //x旋转为y的父亲
    tr[z].s[tr[z].s[1]==y]=x;
    tr.p=z;
    //维护z的儿子位置关系
    pushup(y);//自下向上更新
    pushup(x);
}

void pushup(int x){//更新子树大小
    tr.siz=tr[tr.s[0]].siz+tr[tr.s[1]].siz+tr.cnt;
}

Splay 伸展操作，将链伸展为树，压缩树高，分为单旋和双旋

将传入的节点所在链进行伸展并把 $x$ 旋转到 $k$ 的下方 ，如果链上有两个节点，那么执行单旋，否则执行双旋

需要一直执行伸展旋转操作，$x$ 旋转到根节点时树高被压缩到最小

定义 $y$ 表示 $x$ 的父亲，$z$ 表示 $y$ 的父亲

单旋：

如上图展示，$x$ 通过旋转一次就能变为 $y$ 的父亲

双旋直线型：

当链上没有折线时，需要先旋转 $y$，再旋转 $x$

双旋折线型：

链上有折线时，通过两次旋转 $x$ 操作，可以将树高压缩一次，并维护的二叉树的性质

void splay(int x,int k){
    while(tr.p!=k){//一直旋转到k节点的下方
        int y=tr.p,z=tr[y].p;
        if (z!=k)//判断单旋还是双旋
            (tr[y].s[0]==x)^(tr[z].s[0]==y)? rotate(x):rotate(y);
        //折线型旋转y，直线型旋转x
        rotate(x);
    }
    if (k==0) root=x;//更新根节点
}

Find 查找操作，查询传入的 $val$ ，并把有这个权值的节点旋转到根节点上

如果不存在 $val$ 元素，则会将与 $val$ 最接近的点旋转到根节点上，这样做的原因是为了方便查找前后驱

基于平衡二叉树的性质，根据值的大小判断搜索左子树还是右子树

void find(int v){
    int x=root;//从根节点进入
    while (tr.s[v>tr.v]&&v!=tr.v)
    //v大于当前节点的权值，搜索右子树，否则搜索左子树
        x=tr.s[v>tr.v];//走到儿子节点
    splay(x,0);//伸展到根节点
}

Insert插入操作，将传入的 $val$ 放进平衡树中并维持平衡性

从根节点进入，根据 $val$ 的大小向下移动，当走到空节点或与 $val$ 权值相同的节点时停止，然后做插入操作

void insert(int v){
    int x=root,p=0;//从根节点进入
    while (x&&tr.v!=v){
        p=x;
        x=tr.s[v>tr.v];
    }
    if (x) tr.cnt++;//如果存在权值相同的节点，该节点计数加一
    else{//否则
        x=++idx;//对新权值编号
        tr[p].s[v>tr[p].v]=x;//判断插入左儿子还是右儿子
        tr.init(v,p);//插入新节点，初始化
    }
    splay(x,0);//伸展操作，维持树高
}

Getpre查找前驱操作，查找权值比 $val$ 小的第一个节点

与Find操作结合，先将权值为 $val$ 的节点旋转到根节点上，如果不存在 $val$ 的节点，那就传入最接近他的节点

如果选装上来的根节点比 $val$ 小，那么这个点就是前驱，否则就走左子树然后通过右子树一直逼近

int getpre(int v){
    find(v);
    int x=root;
    if (tr.v<v) return x;//判断旋转上来的根节点是否就是前驱
    x=tr.s[0];//走左子树
    while (tr.s[1]) x=tr.s[1];//右子树无限逼近
    splay(x,0);
    return x;
}

Getsuc查找后驱操作，查找权值比 $val$ 大的第一个节点

int getsuc(int v){
    find(v);
    int x=root;
    if (tr.v>v) return x;
    x=tr.s[1];
    while (tr.s[0]) x=tr.s[0];
    splay(x,0);
    return x;
}

Del删除操作，删去一个权值为 $val$ 的节点

如果在没有特殊出理的平衡树上删除一个节点，需要维护他子树的性质，较难实现

所以考虑将需要删去的节点架空到一个叶子节点上，这样便不需要对子树进行维护

原理是先将 $val$ 的前驱旋转到根节点上，然后将后驱转到前驱的右子树上，那么两者夹住的节点（后驱的左子树），就是需要删除的 $val$ 节点

void del(int v){
    int pre=getpre(v);
    int suc=getsuc(v);
    splay(pre,0);
    splay(suc,pre);
    int del=tr[suc].s[0];
    if (tr[del].cnt>1){
        tr[del].cnt--;
        splay(del,0);
    } 
    else{//如果能被删空，那么就将这个节点移除
        tr[suc].s[0]=0;
        splay(suc,0);
    }
}

Getrank查询排名操作，查询有多少个权值大于 $val$ 的节点

先插入一个权值为 $val$ 的节点，插入操作后，这个节点被旋转到了根节点上，那么他的左子树的大小就是比他小的元素个数

为了能保证查询过程中左右子树都至少有一个节点，所以在平衡树建立时，插入左右哨兵

insert(-Iinf);//最小值哨兵
insert(Iinf);//最大值哨兵

int getrank(int v){
    insert(v);
    int res=tr[tr[root].s[0]].siz;
    del(v);
    return res;
}

Getval查询权值操作，查询节点编号为 $k$ 的权值

仍然从根节点进入，如果左子树非空且剩余排名 $k$ 不大于左子树的大小，那么向左子树查找；否则减去左子树的大小。

如果减去左子树的大小后，剩余排名 $k$ 不大于父节点的节点次数，那么所查询的节点就是父节点；否则减去父节点次数向右子树查找

找到需要的节点后将节点伸展到根上，返回根节点的权值

int getval(int k){
    int x=root;
    while (1){
        int y=tr.s[0];
        if (tr[y].siz+tr.cnt<k){//搜索右子树
            k-=tr[y].siz+tr.cnt;
            x=tr.s[1];
        }else{
            if (tr[y].siz>=k) x=tr.s[0];//搜索左子树
            else break;//找到查询的节点
        }
    }
    splay(x,0);
    return tr.v;
}