upd：忽然发现直接在百度上搜索 splay s p l a y 就会搜索到我这篇文章？小蒟蒻瑟瑟发抖。
因为CSDN这边我基本不会看回复什么的，所以如果有问题还是请移步cnblogs里面吧
Cnblogs里面这篇文章的链接
BST真是神奇的东西。。。
而且种类好多呀。。。
我这个蒟蒻只学会了splay
orzCJ老爷，各种树都会
好好好，不说了，直接说splay。
不知道splay是啥，，你也要知道平衡树是啥。。。
平衡树是一个神奇的数据结构，
对于任意一个节点，左儿子的值比它小，右儿子的值比它大
并且任意一棵子树单独拎出来也是一棵平衡树
就像这样。。。。
各位大佬请原谅我丑陋无比的图
上面这个丑陋的东西就是一棵平衡树，他现在很平衡，是一棵满二叉树，高度正好是logn。。。
但是。。
如果这个丑陋的东西极端一点，他就会变成这样。。。
这张图依然很丑
现在看起来，这个东西一点都不平衡。。。
二叉树退化成了一条链
如果要查询的话，，，最坏情况下就变成了O(n)
这就很尴尬了。。。
各位大佬们为了解决平衡树这个尴尬的问题，想出了各种方法。。
也就是弄出了各种树。。。。（然而cj大佬都会）
然后有一个注明的大佬叫做Tarjan，弄出了splay这个玩意。。。
这个玩意怎么解决上面的问题呢？？？
你是一个平衡树是吧。。。
我把你的节点的顺序修改一下，让你还是一棵平衡树，在这个过程中你的结构就变化了，就可能不再是一条链了。
诶，这个看起来很厉害的感觉。。。
但是，，我怎么说也说不清呀。。
弄张丑陋的图过来
这是一个丑陋的平衡树的一部分
其中XYZ三个是节点，ABC三个是三棵子树
现在这个玩意，我如果想把X弄到Y那个地方去要怎么办，这样的话我就经过了旋转，重构了这棵树的结构，就可能让他变得更加平衡
恩，我们来看看怎么办。。。
X是Y的左儿子，所以X < Y
Y是Z的左儿子，所以Y < Z
所以X < Z，所以如果要把X弄到Y的上面去的话，X就应该放到Y的那个位置
继续看，现在Y > X那么Y一定是X的右儿子
但是X已经有了右儿子B，
根据平衡树我们可以知道X < B < Y
所以我们可以把X的右儿子B丢给Y当做左儿子
而X的左儿子A有A < X < Y < Z显然还是X的左儿子
综上，我们一顿乱搞，原来的平衡树被我们搞成了这个样子
在检查一下
原来的大小关系是
A < X < B < Y < C < Z
把X旋转一下之后大小关系
A < X < B < Y < C < Z
诶，大小关系也没有变
所以之前那棵平衡树就可以通过旋转变成这个样子
并且这个时候还是一棵平衡树
好神奇诶。。。
但是，XYZ的关系显然不仅仅只有这一种
有Y是Z的左儿子 X是Y的左儿子
有Y是Z的左儿子 X是Y的右儿子
有Y是Z的右儿子 X是Y的左儿子
有Y是Z的右儿子 X是Y的右儿子
一共4种情况，大家可以自己画画图，转一转。
如果把上面的图画完了，我们就可以正式的来玩一玩splay了
转完了上面四种情况，我们来找找规律
最明显的一点，我们把X转到了原来Y的位置
也就是说，原来Y是Z的哪个儿子，旋转之后X就是Z的哪个儿子
继续看一看
我们发现，X是Y的哪个儿子，那么旋转完之后，X的那个儿子就不会变
什么意思？
看一看我上面画的图
X是Y的左儿子，A是X的左儿子，旋转完之后，A还是X的左儿子
这个应该不难证明
如果X是Y的左儿子，A是X的左儿子
那么A < X < Y旋转完之后A还是X的左儿子
如果X是Y的右儿子，A是X的右儿子
那么A > X > Y 只是把不等式反过来了而已
再看一下，找找规律
如果原来X是Y的哪一个儿子，那么旋转完之后Y就是X的另外一个儿子
再看看图
如果原来X是Y的左儿子，旋转之后Y是X的右儿子
如果原来X是Y的右儿子，旋转之后Y是X的左儿子
这个应该也很好证明吧。。。
如果X是右儿子 X > Y，所以旋转后Y是X的左儿子
如果X是左儿子 Y > X，所以旋转后Y是X的右儿子
所以总结一下：
1.X变到原来Y的位置
2.Y变成了 X原来在Y的 相对的那个儿子
3.Y的非X的儿子不变 X的 X原来在Y的 那个儿子不变
4.X的 X原来在Y的 相对的 那个儿子 变成了 Y原来是X的那个儿子
啊，，，写出来真麻烦，用语言来写一下
其中t是树上节点的结构体，ch数组表示左右儿子，ch[0]是左儿子，ch[1]是右儿子，ff是父节点
void rotate(int x)//X是要旋转的节点
{int y=t[x].ff;//X的父亲int z=t[y].ff;//X的祖父int k=t[y].ch[1]==x;//X是Y的哪一个儿子 0是左儿子 1是右儿子t[z].ch[t[z].ch[1]==y]=x;//Z的原来的Y的位置变为Xt[x].ff=z;//X的父亲变成Zt[y].ch[k]=t[x].ch[k^1];//X的与X原来在Y的相对的那个儿子变成Y的儿子t[t[x].ch[k^1]].ff=y;//更新父节点t[x].ch[k^1]=y;//X的 与X原来相对位置的儿子变成 Yt[y].ff=x;//更新父节点
}上面的代码用了很多小小小技巧
比如t[y].ch[1]==x
t[y].ch[1]是y的右儿子，如果x是右儿子，那么这个式子是1，否则是0，也正好对应着左右儿子
同样的k^1，表示相对的儿子，左儿子0^1=1 右儿子1^1=0
好了，这就是一个基本的旋转操作（别人讲的
继续看接下来的东西
现在考虑一个问题
如果要把一个节点旋转到根节点（比如上面的Z节点呢）
我们是不是可以做两步，先把X转到Y再把X转到Z呢？
我们来看一看
一个这样的Splay
把X旋转到Y之后
再接着把X旋转到Z之后
好了，这就是对X连着旋转两次之后的Splay，看起来似乎没有什么问题。
但是，我们现在再来看一看
原图中的Splay有一条神奇链： Z->Y->X->B
然后再来看一看旋转完之后的Splay
也有一条链X->Z->Y->B
也就是说
如果你只对X进行旋转的话，
有一条链依旧存在，
如果是这样的话，splay很可能会被卡。
好了，
显然对于XYZ的不同情况，可以自己画图考虑一下，
如果要把X旋转到Z的位置应该如何旋转
归类一下，其实还是只有两种：
第一种，X和Y分别是Y和Z的同一个儿子
第二种，X和Y分别是Y和Z不同的儿子
对于情况一，也就是类似上面给出的图的情况，就要考虑先旋转Y再旋转X
对于情况二，自己画一下图，发现就是对X旋转两次，先旋转到Y再旋转到X
这样一想，对于splay旋转6种情况中的四种就很简单的分了类
其实另外两种情况很容易考虑，就是不存在Z节点，也就是Y节点就是Splay的根了
此时无论怎么样都是对于X向上进行一次旋转
那么splay的旋转也可以很容易的简化的写出来
void splay(int x,int goal)//将x旋转为goal的儿子，如果goal是0则旋转到根
{while(t[x].ff!=goal)//一直旋转到x成为goal的儿子{int y=t[x].ff,z=t[y].ff;//父节点祖父节点if(z!=goal)//如果Y不是根节点，则分为上面两类来旋转(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);//这就是之前对于x和y是哪个儿子的讨论rotate(x);//无论怎么样最后的一个操作都是旋转x}if(goal==0)root=x;//如果goal是0，则将根节点更新为x
}这样写多简单，比另外一些人写得分6种情况讨论要简单很多。
应SYC大佬要求，继续补充内容。
先是查找find操作
从根节点开始，左侧都比他小，右侧都比他大，
所以只需要相应的往左/右递归
如果当前位置的val已经是要查找的数
那么直接把他Splay到根节点，方便接下来的操作
类似于二分查找，
所以时间复杂度O(logn)
inline void find(int x)//查找x的位置，并将其旋转到根节点
{int u=root;if(!u)return;//树空while(t[u].ch[x>t[u].val]&&x!=t[u].val)//当存在儿子并且当前位置的值不等于xu=t[u].ch[x>t[u].val];//跳转到儿子，查找x的父节点splay(u,0);//把当前位置旋转到根节点
}下一个Insert操作
往Splay中插入一个数
类似于Find操作，只是如果是已经存在的数，就可以直接在查找到的节点的进行计数
如果不存在，在递归的查找过程中，会找到他的父节点的位置，
然后就会发现底下没有啦。。。
所以这个时候新建一个节点就可以了
inline void insert(int x)//插入x
{int u=root,ff=0;//当前位置u，u的父节点ffwhile(u&&t[u].val!=x)//当u存在并且没有移动到当前的值{ff=u;//向下u的儿子，父节点变为uu=t[u].ch[x>t[u].val];//大于当前位置则向右找，否则向左找}if(u)//存在这个值的位置t[u].cnt++;//增加一个数else//不存在这个数字，要新建一个节点来存放{u=++tot;//新节点的位置if(ff)//如果父节点非根t[ff].ch[x>t[ff].val]=u;t[u].ch[0]=t[u].ch[1]=0;//不存在儿子t[tot].ff=ff;//父节点t[tot].val=x;//值t[tot].cnt=1;//数量t[tot].size=1;//大小}splay(u,0);//把当前位置移到根，保证结构的平衡
}继续，，，
前驱/后继操作Next
首先就要执行Find操作
把要查找的数弄到根节点
然后，以前驱为例
先确定前驱比他小，所以在左子树上
然后他的前驱是左子树中最大的值
所以一直跳右结点，直到没有为止
找后继反过来就行了
inline int Next(int x,int f)//查找x的前驱(0)或者后继(1)
{find(x);int u=root;//根节点，此时x的父节点（存在的话）就是根节点if(t[u].val>x&&f)return u;//如果当前节点的值大于x并且要查找的是后继if(t[u].val<x&&!f)return u;//如果当前节点的值小于x并且要查找的是前驱u=t[u].ch[f];//查找后继的话在右儿子上找，前驱在左儿子上找while(t[u].ch[f^1])u=t[u].ch[f^1];//要反着跳转，否则会越来越大（越来越小）return u;//返回位置
}还有操作呀/。。。
删除操作
现在就很简单啦
首先找到这个数的前驱，把他Splay到根节点
然后找到这个数后继，把他旋转到前驱的底下
比前驱大的数是后继，在右子树
比后继小的且比前驱大的有且仅有当前数
在后继的左子树上面，
因此直接把当前根节点的右儿子的左儿子删掉就可以啦
inline void Delete(int x)//删除x
{int last=Next(x,0);//查找x的前驱int next=Next(x,1);//查找x的后继splay(last,0);splay(next,last);//将前驱旋转到根节点，后继旋转到根节点下面//很明显，此时后继是前驱的右儿子，x是后继的左儿子，并且x是叶子节点int del=t[next].ch[0];//后继的左儿子if(t[del].cnt>1)//如果超过一个{t[del].cnt--;//直接减少一个splay(del,0);//旋转}elset[next].ch[0]=0;//这个节点直接丢掉（不存在了）
}还剩下一些splay的基本操作
先留个坑，以后再慢慢补。。。
