SPLAY

SPLAY是一种平衡树，特点是每次操作都将操作节点旋转到根节点。

维护的信息有大小sz,次数cnt,值val,父亲节点fa[MAXN],儿子节点ch[MAXN][2]

全局变量有：根节点rt,节点编码总数tot

代码如下：

#include <iostream>

using namespace std;
const int MAXN=1e5+2;

int rt,tot,fa[MAXN],ch[MAXN][2],val[MAXN],cnt[MAXN],sz[MAXN];

//更新信息
void maintain(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];}

//确定是左节点还是右节点
bool get(int x){return x==ch[fa[x]][1];}

//清空信息
void clear(int x){fa[x]=ch[x][0]=ch[x][1]=val[x]=cnt[x]=sz[x]=0;}

//旋转节点
void rotate(int x){
 /*四种情况的一种   
        z               z
       /               /
      y		--->      x
     /               / \
    x               a   y
   / \                   \
  a   b                   b 
*/    
    int y=fa[x],z=fa[y],chk=get(x);
    
    ch[y][chk]=ch[x][chk^1];
    if(ch[x][chk^1])fa[ch[x][chk^1]]=y;
    
    ch[x][chk^1]=y;
    fa[y]=x;

    if(z)ch[z][y==ch[z][1]]=x;
    fa[x]=z;

    maintain(y);
    maintain(x);
}

//旋转x到根节点
void splay(int x){
    //若fa[f]没有，直接rotate(x)
    //若有，根据x,f,fa[f]的位置，有四种情况，用一种代码便可以解决，一种位置关系如下
/*
      fa[f]           x
      /                \
     f		--->        f
    /                    \
   x                     fa[f]
*/
    for(int f=fa[x];f=fa[x],f;rotate(x)){
        if(fa[f])rotate(get(x)==get(f)?f:x);
    }
    rt=x;
}

void ins(int k){
    if(!rt){
        //若根节点为空，直接建立
        val[++tot]=k;
        cnt[tot]++;
        rt=tot;
        maintain(rt);
        return;
    }
    int cur=rt,f=0;
    while(1){
        if(val[cur]==k){
            //若值相等，直接cnt++
            cnt[cur]++;
            maintain(cur);
            maintain(f);
            splay(cur);
            break;
        }
        //搜索儿子
        f=cur;
        cur=ch[cur][val[cur]<k];
        if(!cur){
            //若找到最后是空，则建立节点
            val[++tot]=k;
            cnt[tot]++;
            fa[tot]=f;
            ch[f][val[f]<k]=tot;
            maintain(tot);
            maintain(f);
            splay(tot);
            break;
        }
    }
}

int rk(int k){
    int res=0,cur=rt;
    while(1){
        if(val[cur]>k){
            //搜索左儿子
            cur=ch[cur][0];
        }else{
            res+=sz[ch[cur][0]];
            if(val[cur]==k){
                //找到返回
                splay(cur);
                return res+1;
            }
            res+=cnt[cur];
            //搜索右儿子
            cur=ch[cur][1];
        }
    }
}

int kth(int k){
    int cur=rt;
    while(1){
        if(ch[cur][0]&&k<=sz[ch[cur][0]]){
            //搜索左儿子
            cur=ch[cur][0];
        }else{
            k-=sz[ch[cur][0]]+cnt[cur];
            if(k<=0){
                //找到了
                splay(cur);
                return val[cur];
            }
            //搜索右儿子
            cur=ch[cur][1];
        }
    }
}

int pre(){
    int cur=ch[rt][0];
    if(!cur)return cur;//前置为空
    while(ch[cur][1])cur=ch[cur][1];
    splay(cur);
    return cur;
}

int nxt(){
    int cur=ch[rt][1];
    if(!cur)return cur;//后继为空
    while(ch[cur][0])cur=ch[cur][0];
    splay(cur);
    return cur;
}

void del(int k){
    //先将值为k的节点找到并splay操作
    rk(k);
    if(cnt[rt]>1){
        //若cnt>1，直接--
        cnt[rt]--;
        maintain(rt);
        return;
    }
    if(!ch[rt][0]&&!ch[rt][1]){
        //左右儿子都没有，直接清空
        clear(rt);
        rt=0;
        return;
    }
    if(!ch[rt][0]){
        //如果没有左儿子，直接删除，右儿子作为根节点
        int cur=rt;
        rt=ch[rt][1];
        fa[rt]=0;
        clear(cur);
        return;
    }
    if(!ch[rt][1]){
        //如果没有右儿子，直接删除，左儿子作为根节点
        int cur=rt;
        rt=ch[rt][0];
        fa[rt]=0;
        clear(cur);
        return;
    }
    //两个儿子都在的话，
    //将原根节点的前置的右儿子设置为原根节点的右儿子
    int cur=rt,x=pre();//求前置的时候已经splay操作了，rt=x
    fa[ch[cur][1]]=x;
    ch[x][1]=ch[cur][1];
    clear(cur);
    maintain(rt);//只需再更新rt的信息
}

int main(){
	//test
    ins(1);
    ins(2);
    ins(3);
    ins(114);
    ins(514);
    ins(1919);
    cout<<rk(114)<<endl;
    cout<<kth(3)<<endl;
    del(114);
    del(3);
    cout<<rk(2)<<endl;
    cout<<kth(3)<<endl;
    return 0;
}

总结：SPLAY支持了基本操作，例如查询rank和kth_element，是一种较简单的平衡树

动画：SPLAY Tree