所謂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);		}	}}