关于平衡树（Splay）的一些总结

        所谓Splay Tree一是这样一种二叉树：对于任意一个节点，节点所维护的值大于它的左子树的所有值，而小于它的右子树的所有值，这样的一棵树平衡树叫Splay Tree。

        和所有的平衡树一样，Splay的最基本操作是rotate。要维持一棵树的平衡，使得每次操作的复杂度均摊能有logn级别，需要我们不断的调整树的形态，rotate操作就能实现这样的功能。若某一节点x为y的左儿子，那么rotate之后他们的父子关系改变，但仍然满足Splay的性质，具体如图：

        可以看出左旋和右旋还是有一定区别的，但是最后都能达到目的。x以及x的子树都比y小，故y的左儿子变为x的右儿子，y变成x的右儿子……具体代码如下(对于rotate操作有些人把左旋右旋利用位运算和bool合并了，但是这样看起来代码简洁，但是常数比较大，于是我便舍弃了这种写法)：

inline void rotate(int x){	int fa=tree[x].fa,grand=tree[fa].fa;				//grand为爷爷，在旋转时爷爷若存在也要做相应变化	if (get(x)) 							//get(x)判断x是左儿子还是右儿子，x是右儿子则左旋	{		tree[fa].r=tree[x].l;		tree[tree[fa].r].fa=fa;		tree[x].l=fa;	} else							  	//左儿子右旋	{		tree[fa].l=tree[x].r;		tree[tree[fa].l].fa=fa;		tree[x].r=fa;	}	tree[x].fa=grand;						//修改父子关系	tree[fa].fa=x;	if (grand) 							//判断并修改爷爷	{		if (tree[grand].r==fa) tree[grand].r=x;		else if (tree[grand].l==fa) tree[grand].l=x;		//注意一定是else if		}}
        完成了rotate，接下来就是splay了，所谓splay操作其实就是把某一个点通过不断的旋转，把它变为根结点，这样的好处就是方便对该点进行操作，这个作用在以后会凸显出来，没什么好说的，操作简单直接上代码：
inline void splay(int x){	for(;tree[x].fa;rotate(x));					//很有特色的写法，好好琢磨	root=x;								//注意变更整棵树的root}
这里有一个小小的疑问，看了其他大牛的blog，有些说儿子父亲爷爷三点一线的情况要特殊判断，但是博主试了几道题没有特判也对了，于是便省去了特判。若有大牛能解释为什么需要特判我将不胜感激。
        然后就是基本的insert操作了，要insert首先得找对该节点的存放位置，根据大小关系，若num小于当前点则肯定在左子树，若等于则就是该点，若大于则是在右子树，代码：
inline void insert(int x){	if (root==0)							//若当前为空树则直接加	{		clear(1);						//clear，清除某点		tree[++sz].num=x;		tree[sz].size=tree[sz].cnt=1;				//size为该子树的节点数目，cnt为同一数值数字数目		root=sz; return;					//sz为整棵树的节点数目	} 	int i=root,fa=0;	while (1)	{		if (tree[i].num==x)					//相等，找到位置		{			tree[i].cnt++;			splay(i);					//目前并没有理解为什么这里要splay			return;		}		fa=i;		i=(x>tree[i].num?tree[i].r:tree[i].l);			//按大小找		if (i==0)						//该点为被添加过，新建节点		{			sz++; 			clear(sz);			tree[sz].num=x;			tree[sz].cnt=tree[sz].size=1;			tree[sz].fa=fa;			(x>tree[fa].num?tree[fa].r:tree[fa].l)=sz;	//设置父亲								splay(sz);					//也不理解为什么要splay，但是不加会错			return;		}	}}
        find操作则是找所有数中第x小(大)的数字，也是一样利用二分在树上一半一半的找。
inline int find(int x)                   				//找数字x在所有数字中的排位，返回排位 {	int ans=0,i=root;	while (1)		if (x>=tree[i].num)		{			ans+=(tree[i].l?tree[tree[i].l].size:0);	//若无左儿子则加0			if (x==tree[i].num) 			{				splay(i);				return ans+1;			}			ans+=tree[i].cnt;			i=tree[i].r;		} else i=tree[i].l;}
      del操作，删除第x小(大)的点，与insert类似，先找到位置令locate=find(x)，然后clear，并维护左右儿子的性质。
inline void del(int x){	int locate=find(x);			if (tree[root].cnt>1) 	{		tree[root].cnt--;		return;	}	if ((!tree[root].l)&&(!tree[root].r))	{		clear(root);		root=0;		return;	}	if (!tree[root].l)	{		int old=root;		root=tree[old].r;		tree[root].fa=0;		clear(old);		return;	}	if (!tree[root].r)	{		int old=root;		root=tree[old].l;		tree[root].fa=0;		clear(old);		return;	}	int left=PRe(),old=root;	splay(left);	tree[tree[old].r].fa=root;	tree[root].r=tree[old].r;	clear(old);}
        pre和next操作分别作用是找某个数字x的前驱和后继，即比该数大一个小一个的数字，实现该操作只需先把x插入树中，再splay把x变为根，然后再找前驱和后继，最后删掉x即可。
inline int pre(){	int i=tree[root].l;						//根的左儿子一直往右就是前驱，后继也是类似，就不贴上来了	while (tree[i].r) i=tree[i].r;	return i;}
        总的来说splay就是这几大操作，真正应用起来多是会结合其他的算法，毕竟程序=数据结构+算法。然后要注意灵活运用就是了，还有Splay Tree 的复杂度虽然几乎都是均摊的logn，但实际它的常数比较大，所以要注意。
        最后，我好像理解了，很多操作里的splay看似可有可无，但好像就是不断的splay才能进行均摊，然后降低复杂度，好吧，我真的不会算复杂度……
        附上模板题：BZOJ 3224
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1. 插入x数2. 删除x数(若有多个相同的数，因只删除一个)3. 查询x数的排名(若有多个相同的数，因输出最小的排名)4. 查询排名为x的数5. 求x的前驱(前驱定义为小于x，且最大的数)6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598
Sample Output
10646584185492737
HINT
1.n的数据范围：n<=1000002.每个数的数据范围：[-1e7,1e7]
代码风格勿喷……
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cmath>#include<cstring>#include<iomanip>#define LL long long#define INF 2147483647#define ENT putchar('/n')#define up(_i,_a,_b) for (int _i=_a;_i<=_b;_i++)#define down(_i,_a,_b) for (int _i=_a;_i>=_b;_i--)#define efor(_i,_a) for (int _i=ls[_a];_i!=0;_i=g[_i].next)#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);using namespace std;inline LL read(){         LL f=1,d=0;char s=getchar();         while (s<'0'||s>'9'){if (s=='-') f=-1;s=getchar();}         while (s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}         return f*d;}inline LL readln(){       LL f=1,d=0;char s=getchar();       while (s<'0'||s>'9'){if (s=='-') f=-1;s=getchar();}       while (s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}       while (s!='/n') s=getchar();       return f*d;}inline void write(LL x){    if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;    int len=0,buf[20];while(x)buf[len++]=x%10,x/=10;    int i=len-1; while (i>=0) {putchar(buf[i--]+'0');}return;}inline void writeln(LL x) {write(x);ENT;}struct node{	int l,r,fa,num,cnt,size;   //cnt为该关键字出现次数，size为子树大小 } tree[100010];int root,sz;                  //sz为整棵树的大小 inline void clear(int x){	tree[x].l=tree[x].r=0;	tree[x].fa=tree[x].num=0;	tree[x].cnt=tree[x].size=0;	} inline int get(int x)        //看x是左儿子还是右儿子 {	return tree[tree[x].fa].r==x;}inline void update(int x){	if (x)	{		tree[x].size=tree[x].cnt;		if (tree[x].l) tree[x].size+=tree[tree[x].l].size;		if (tree[x].r) tree[x].size+=tree[tree[x].r].size;	}}inline void rotate(int x){	int fa=tree[x].fa,grand=tree[fa].fa;	if (get(x))	{		tree[fa].r=tree[x].l;		tree[tree[fa].r].fa=fa;		tree[x].l=fa;	} else	{		tree[fa].l=tree[x].r;		tree[tree[fa].l].fa=fa;		tree[x].r=fa;	}	tree[x].fa=grand;	tree[fa].fa=x;	if (grand) 	{		if (tree[grand].r==fa) tree[grand].r=x;		                  else tree[grand].l=x;	}	update(fa); 	update(x);}inline void splay(int x){	for(;tree[x].fa;rotate(x));	root=x;}inline void insert(int x){	if (root==0)	{		clear(1);		tree[++sz].num=x;		tree[sz].size=tree[sz].cnt=1;		root=sz; return;	} 	int i=root,fa=0;	while (1)	{		if (tree[i].num==x)		{			tree[i].cnt++;			update(i);			update(fa);			splay(i);			return;		}		fa=i;		i=(x>tree[i].num?tree[i].r:tree[i].l);		if (i==0)		{			sz++; 			clear(sz);			tree[sz].num=x;			tree[sz].cnt=tree[sz].size=1;			tree[sz].fa=fa;			(x>tree[fa].num?tree[fa].r:tree[fa].l)=sz;			update(fa);			splay(sz);			return;		}	}}inline int find(int x){	int ans=0,i=root;	while (1)		if (x>=tree[i].num)		{			ans+=(tree[i].l?tree[tree[i].l].size:0);			if (x==tree[i].num) 			{				splay(i);				return ans+1;			}			ans+=tree[i].cnt;			i=tree[i].r;		} else i=tree[i].l;}inline int findx(int x){	int i=root;	while (1)		if ((tree[i].l)&&(x<=tree[tree[i].l].size)) i=tree[i].l;		else		{			int k=(tree[i].l?tree[tree[i].l].size:0)+tree[i].cnt;			if (x<=k) return tree[i].num;			i=tree[i].r; x-=k;		}}inline int pre(){	int i=tree[root].l;	while (tree[i].r) i=tree[i].r;	return i;}inline int next(){	int i=tree[root].r;	while (tree[i].l) i=tree[i].l;	return i;}inline void del(int x){	int locate=find(x);	if (tree[root].cnt>1) 	{		tree[root].cnt--;		return;	}	if ((!tree[root].l)&&(!tree[root].r))	{		clear(root);		root=0;		return;	}	if (!tree[root].l)	{		int old=root;		root=tree[old].r;		tree[root].fa=0;		clear(old);		return;	}	if (!tree[root].r)	{		int old=root;		root=tree[old].l;		tree[root].fa=0;		clear(old);		return;	}	int left=pre(),old=root;	splay(left);	tree[tree[old].r].fa=root;	tree[root].r=tree[old].r;	clear(old);	update(root);}int main(){	int n;	n=read();	up(i,1,n)	{		int opt,x;		opt=read();		x=read();		if (opt==1) insert(x);		if (opt==2) del(x);		if (opt==3) writeln(find(x));		if (opt==4) writeln(findx(x));		if (opt==5) 		{			insert(x);			find(x);			writeln(tree[pre()].num);			del(x);		}		if (opt==6)		{			insert(x);			find(x);			writeln(tree[next()].num);			del(x);		}	}}