所謂Splay Tree一是這樣一種二叉樹：對(duì)于任意一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)所維護(hù)的值大于它的左子樹的所有值，而小于它的右子樹的所有值，這樣的一棵樹平衡樹叫Splay Tree。

        和所有的平衡樹一樣，Splay的最基本操作是rotate。要維持一棵樹的平衡，使得每次操作的復(fù)雜度均攤能有l(wèi)ogn級(jí)別，需要我們不斷的調(diào)整樹的形態(tài)，rotate操作就能實(shí)現(xiàn)這樣的功能。若某一節(jié)點(diǎn)x為y的左兒子，那么rotate之后他們的父子關(guān)系改變，但仍然滿足Splay的性質(zhì)，具體如圖：

        可以看出左旋和右旋還是有一定區(qū)別的，但是最后都能達(dá)到目的。x以及x的子樹都比y小，故y的左兒子變?yōu)閤的右兒子，y變成x的右兒子……具體代碼如下(對(duì)于rotate操作有些人把左旋右旋利用位運(yùn)算和bool合并了，但是這樣看起來代碼簡(jiǎn)潔，但是常數(shù)比較大，于是我便舍棄了這種寫法)：

inline void rotate(int x){	int fa=tree[x].fa,grand=tree[fa].fa;				//grand為爺爺，在旋轉(zhuǎn)時(shí)爺爺若存在也要做相應(yīng)變化	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;						//修改父子關(guān)系	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操作其實(shí)就是把某一個(gè)點(diǎn)通過不斷的旋轉(zhuǎn)，把它變?yōu)楦Y(jié)點(diǎn)，這樣的好處就是方便對(duì)該點(diǎn)進(jìn)行操作，這個(gè)作用在以后會(huì)凸顯出來，沒什么好說的，操作簡(jiǎn)單直接上代碼：
inline void splay(int x){	for(;tree[x].fa;rotate(x));					//很有特色的寫法，好好琢磨	root=x;								//注意變更整棵樹的root}
這里有一個(gè)小小的疑問，看了其他大牛的blog，有些說兒子父親爺爺三點(diǎn)一線的情況要特殊判斷，但是博主試了幾道題沒有特判也對(duì)了，于是便省去了特判。若有大牛能解釋為什么需要特判我將不勝感激。
        然后就是基本的insert操作了，要insert首先得找對(duì)該節(jié)點(diǎn)的存放位置，根據(jù)大小關(guān)系，若num小于當(dāng)前點(diǎn)則肯定在左子樹，若等于則就是該點(diǎn)，若大于則是在右子樹，代碼：
inline void insert(int x){	if (root==0)							//若當(dāng)前為空樹則直接加	{		clear(1);						//clear，清除某點(diǎn)		tree[++sz].num=x;		tree[sz].size=tree[sz].cnt=1;				//size為該子樹的節(jié)點(diǎn)數(shù)目，cnt為同一數(shù)值數(shù)字?jǐn)?shù)目		root=sz; return;					//sz為整棵樹的節(jié)點(diǎn)數(shù)目	} 	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)						//該點(diǎn)為被添加過，新建節(jié)點(diǎn)		{			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;	//設(shè)置父親								splay(sz);					//也不理解為什么要splay，但是不加會(huì)錯(cuò)			return;		}	}}
        find操作則是找所有數(shù)中第x小(大)的數(shù)字，也是一樣利用二分在樹上一半一半的找。
inline int find(int x)                   				//找數(shù)字x在所有數(shù)字中的排位，返回排位 {	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小(大)的點(diǎn)，與insert類似，先找到位置令locate=find(x)，然后clear，并維護(hù)左右兒子的性質(zhì)。
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操作分別作用是找某個(gè)數(shù)字x的前驅(qū)和后繼，即比該數(shù)大一個(gè)小一個(gè)的數(shù)字，實(shí)現(xiàn)該操作只需先把x插入樹中，再splay把x變?yōu)楦缓笤僬仪膀?qū)和后繼，最后刪掉x即可。
inline int pre(){	int i=tree[root].l;						//根的左兒子一直往右就是前驅(qū)，后繼也是類似，就不貼上來了	while (tree[i].r) i=tree[i].r;	return i;}
        總的來說splay就是這幾大操作，真正應(yīng)用起來多是會(huì)結(jié)合其他的算法，畢竟程序=數(shù)據(jù)結(jié)構(gòu)+算法。然后要注意靈活運(yùn)用就是了，還有Splay Tree 的復(fù)雜度雖然幾乎都是均攤的logn，但實(shí)際它的常數(shù)比較大，所以要注意。
        最后，我好像理解了，很多操作里的splay看似可有可無，但好像就是不斷的splay才能進(jìn)行均攤，然后降低復(fù)雜度，好吧，我真的不會(huì)算復(fù)雜度……
        附上模板題：BZOJ 3224
Description
您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標(biāo)題），來維護(hù)一些數(shù)，其中需要提供以下操作：1. 插入x數(shù)2. 刪除x數(shù)(若有多個(gè)相同的數(shù)，因只刪除一個(gè))3. 查詢x數(shù)的排名(若有多個(gè)相同的數(shù)，因輸出最小的排名)4. 查詢排名為x的數(shù)5. 求x的前驅(qū)(前驅(qū)定義為小于x，且最大的數(shù))6. 求x的后繼(后繼定義為大于x，且最小的數(shù))
Input
第一行為n，表示操作的個(gè)數(shù),下面n行每行有兩個(gè)數(shù)opt和x，opt表示操作的序號(hào)(1<=opt<=6)
Output
對(duì)于操作3,4,5,6每行輸出一個(gè)數(shù)，表示對(duì)應(yīng)答案
Sample Input
101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598
Sample Output
10646584185492737
HINT
1.n的數(shù)據(jù)范圍：n<=1000002.每個(gè)數(shù)的數(shù)據(jù)范圍：[-1e7,1e7]
代碼風(fēng)格勿噴……
#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為該關(guān)鍵字出現(xiàn)次數(shù)，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);		}	}}