普通平衡树学习笔记之Splay算法

平衡树是二叉搜索树和堆合并构成的数据结构，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
这里仅仅说明一下平衡树中的\(Splay\)算法

进入正题

平衡树中有许多种类：红黑树、\(AVL\)树，伸展树，\(Treap\)等等，但是\(Splay\)算法算是可用性很强的一种了。也就是说比较稳定。

在\(Splay\)算法中，一个处处都要用到的东西就是旋转，即将当前节点与其前边一个节点依次旋转到目标位置。由于这个树是一个二叉搜索树，所以旋转之后要保证性质不变。我们就需要找到当前节点的父亲和爷爷节点，然后先更新爷爷节点与当前节点之间的关系，然后将父亲节点与该节点所属关系的另一个子树连起来，最后再处理一下该节点和父亲节点的关系。

我们举个例子（毕竟不太好理解）我们设这三个点分别为\(x,y,z\)，从左往右分别是后一个的儿子，我们先把图画一下（\(x\)的子节点我随便用一堆东西表示）：

在这里\(x\)是\(y\)的左节点。那么我们下一步就是把\(x\)变为\(z\)的子节点，也就是把\(y\)换下来。这一步很简单，变成了下边这样：

然后就是关键了，因为把\(x\)旋转上来，\(x\)也是有子节点的，所以我们需要进一步处理。首先记录一下\(x\)是\(y\)节点的左还是右儿子，在这个例子里是左儿子，因为我们不能破坏这个树的顺序和性质，所以就需要让\(y\)的右儿子不变且所有满足性质的比\(x\)小的他的左儿子还是\(x\)的左儿子，而\(y\)的左儿子变成\(x\)的右儿子，也就是下边这个图：（刚刚没有\(y\)的右节点，现在加上，编号与之前的不同，自己理解理解\(qwq\)）：

类似的一个图，这样就完成了一次旋转。最后不样忘记也是需要\(pushup\)的，来维护点的儿子数量和自己的数量。
下边放一下\(Splay\)和旋转的代码

void rotate(int x){//旋转 int y=t[x].fa; int z=t[y].fa; int k=t[y].ch[1]==x;//找到x是y的左还是右节点，便于进行上文中所说操作 t[z].ch[t[z].ch[1]==y]=x;//以下都是上边说过的操作。 t[x].fa=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].fa=y; t[x].ch[k^1]=y; t[y].fa=x; pushup(y); pushup(x); } void splay(int x,int goal){//旋转 while(t[x].fa!=goal){//父亲节点不是目标 int y=t[x].fa; int z=t[y].fa; if(z!=goal){//爷爷节点也不是目标 (t[y].ch[0]==x)^(t[z].ch[0]==x)?rotate(x):rotate(y);//其中一个点的左儿子是x就翻转x，不然翻转y（因为树有序，不能破坏性质） }//上边这句话还需要细细钻研，本题解以后还会完善 rotate(x); } if(goal == 0){//到了根节点的话让根节点更新 root = x; } } 一些操作

上边把\(Splay\)的操作说了一遍，也就是关键的旋转应该比较清晰了，下边我们就需要进行一些操作了。
平衡树有许多可以进行的操作：删除，插入，查询一个值\(x\)的排名，查询\(x\)排名的值，还有值\(x\)的前驱和后继。(前驱定义为小于 \(x\)，且最大的数,后继定义为大于 \(x\)且最小的数)。这些都需要上边的旋转，所以旋转明白了，这些也就比较容易了。首先是结构体的定义：

struct Node { int ch[2];//子节点 int fa;//父节点 int cnt;//数量 int val;//值 int son;//儿子数量 }t[maxn]; \(1\)、插入

我们肯定要从根节点开始向下找到符合这个值的点，或者新建一个点，那么我们首先另\(u\)为根节点，其父亲为\(0\)，然后如果有根且插入的值不是当前节点的值，那么我们就需要向子节点扩展，这里我的扩展比较巧妙，因为儿子只有左右分别用\(0\)、\(1\)表示，所以直接用判断来找到底是左还是右，也就是这样的式子：\(x>t[u].val\)。如果大于的话，就是右儿子。否则就是左儿子。所以直接更新到当前节点的儿子节点。
当跳出向下扩展的循环，就说明当前点值就是要插入的值，我们只需要将大小加一就行。如果没有这样的节点，那么就新建一个节点，然后将父亲的儿子节点置为当前节点，而左右儿子的判断如上文所说。其余的东西都是初始化，具体看代码，最后不要忘了再将当前节点\(Splay\)到根（几乎每种操作都需要\(Splay\)，查询前驱后继和排名的值不用）：

void Add(int x){ int u=root,fa=0; while(u&&t[u].val!=x){ fa=u; u=t[u].ch[x>t[u].val]; } if(u){//有的话直接大小加一 t[u].cnt++; } else{//没有该值的节点 u=++tot; if(fa)t[fa].ch[x>t[fa].val]=u; t[tot].ch[1]=0; t[tot].ch[0]=0; t[tot].val=x; t[tot].fa=fa; t[tot].cnt=1; t[tot].son=1; } splay(u,0); } \(2\)、查找值为\(x\)的排名：