Splay 学习笔记（未完成）

一个月没写博客了，今后要更加努力啊

Splay Tree 是一种二叉排序树

通过不断旋转以维护单词操作复杂度为log(n)级别

在这里讲述的操作有:插入，删除，查询第k大，rank，前驱后继

旋转分三种情况

1.Zig

2.ZigZig

3.ZigZag

在这里不详细叙述旋转细节，而主要注重代码实现

int son[N][2]; //son[x][0]表示x的左儿子,son[x][1]表示x的右儿子

int f[N]; //f[x]表示x的父亲

int key[N]; //表示x的值

int cnt[N]; //表示x出现次数

int size[N]; //表示以x为根的子树大小

int root; //表示根结点

int sz; //表示整颗树的大小

clear(x)函数，用于删除x后的扫尾工作

void clear(int x){
    son[x][1]=son[x][0]=cnt[x]=f[x]=key[x];
}

get(x)函数，判断x是父亲的左儿子还是右儿子，左返回0右返回1

int get(int x){
    return son[f[x]][1]==x;
}

update(x)函数，用于维护信息的操作

在这里我只会维护子树大小。。

void update(int x){
    if(x){
        size[x]=cnt[x];
        size[x]+=size[son[x][1]];
        size[x]+=size[son[x][0]];
    }
}

rotate(x) 重点的旋转操作

旋转前：

旋转后：

在这里要感谢EternalAlexander神犇制作的绘图工具 OI Painter

比较一下旋转前旋转后，不难发现③号节点被旋转到了原来它的父亲②号节点的位置，并且保持二叉排序树的性质

具有普遍性的讲就是将x结点旋转至x爷爷的儿子下，并且将原来x的父亲变为自己的儿子

步骤1

先找到x的父亲fa 与 x的爷爷(父亲的父亲) ff 并确定x是fa的左儿子还是右儿子

步骤2
将x移到fa的位置，根据大小关系可知

x如果是fa的左儿子，旋转以后fa是x的右儿子
x原来的右儿子变为fa的左儿子


x如果是fa的右儿子，旋转以后fa是x的左儿子 
x原来的左儿子变为fa的右儿子

下文中的w表示x是父亲的左儿子还是右儿子，左儿子为0右儿子为1

inline void rotate(int x){
    int fa=f[x],ff=f[fa],w=get(x);

    son[fa][w]=son[x][w^1];
    f[son[fa][w^1]]=fa;

    son[x][w^1]=fa;
    f[fa]=x;

    f[x]=ff;
    if(ff) son[ff][son[ff][1]==fa]=x;
}

splay(x) 函数
无数个ratote嵌套

inline void splay(int x){
   for(;f[x];rotate(x)){
       if(f[f[x]]&&(get(f[x])==get(x)))
            rotate(f[x]);
   }
   root=x;
}

insert(x) 插入函数 x为值

如果是第一个节点就改为root，如果不是就向下找，添加，然后splay它

inline void insert(x){
    if(!root){
        root=++sz;cnt[sz]=1;son[sz][1]=son[sz][0]=0;key[sz]=x;size[x]=1;
        return ;
    }
    int now=root,fa=0;
    while(1){
        if(key[now]==x){
            cnt[now]++;
            update(now);update(fa);
            splay(now);
            return;
        }
        fa=now,now=son[fa][key[now]<x];
        if(!now){
            sz++;
            son[sz][1]=son[sz][0]=0;
            size[sz]=cnt[sz]=1;
            son[fa][key[fa]<x]=sz;
            key[sz]=x;
            f[sz]=fa;
            update(fa);
            splay(fa);
            return;
        }
    }
}

未完待续..