【数据结构】Splay_Tree(伸展树)

大家好，这是本人的第一篇博客，第一篇就写Splay_Tree好紧张QuQ，希望大家多多包涵，如果有错请不要打我TuT。

Splay_Tree的中文名字叫做伸展树【明明意思都一样，可是这个中文听上去就是变低端了…大概是翻译B格不够高的原因…怎么不叫飘逸树什么的…就算伸懒腰树也比这个萌多了呀⊙﹏⊙】，是一种优秀的假装自己属于平衡树家族的数据结构。

先说一下二叉检索树（Binary_Search_Tree）【大概是我知道怎么读Binary，所以觉得这个英文一点儿也不高端(￣^￣)ゞ…】，这个树就是一棵满足对于所有节点，左孩子节点小于它，右孩子节点大于它的树，这样就可以在这棵树上干很多奇奇怪怪的事情了（比如插入呀删除呀求第k小数呀）。

然而二叉检索树上操作的时间复杂度只正比于树的最大深度，于是如果树退化成了链，就会变得非常的凄惨了T^T。那么如何把瘦高的长为n的链pia成矮胖的高度只有差不多log₂n的树呢？为了解决这个问题，平衡树闪亮登场了。平衡树嘛，顾名思义，就是通过一些很高端的操作来把树pia扁，让每个节点的左右子树的高度最多相差1的数据结构了。

而其中ST【我才不管什么SparseTable，我就要这么简称SplayTree(╯°Д°）╯︵/(.□.)】就是一种假的平衡树。为什么是假的？因为它根本就不平衡…但是ST的操作的均摊复杂度却真的是logn级别的。

虽然ST的常数大到远超线段树，甚至在平衡树家族中都属于能跑能跳思维好的那种，但是实在是架不住『编程复杂度低』这样的好事情，再加上它可以支持一些其他大多数平衡树不支持的奇怪操作（比如区间反向什么的），自然就成了我们这些懒人的首选。

ST之所以得名，就是因为它是用Splay操作把树pia扁的。这个操作之所以能完成，是因为在二叉检索树中可以通过Zig操作和Zag操作来交换一堆父子关系（不是交换父子位置啦），并且调整子树，让它们仍然维持二叉检索性。

//rot为根节点编号,tot为节点总数,Vl记录节点的值,Fa[M]是父节点编号,Ls[M]是左子节点编号,Rs[M]是右子节点编号,Sz[M]是以这个点为根的子树大小。

inline void Update(int u){Sz[u]=Sz[Ls[u]]+Sz[Rs[u]]+1;}
inline void Zig(int u){
	int v=Fa[u],w=Fa[v]; 
	Ls[w]==v?Ls[w]=u:Rs[w]=u;Fa[u]=w;
	Ls[v]=Rs[u];Fa[Rs[u]]=v;Rs[u]=v;Fa[v]=u;
	Update(u);Update(v);
}
inline void Zag(int u){
	int v=Fa[u],w=Fa[v];
	Ls[w]==v?Ls[w]=u:Rs[w]=u;Fa[u]=w;
	Rs[v]=Ls[u];Fa[Ls[u]]=v;Ls[u]=v;Fa[v]=u;
	Update(u);Update(v);
}

Splay操作就是把一个节点Zig、Zag到它的祖先节点，在过程中顺便（其实这是主要目的，才不是顺便呢）把树pia扁。这就涉及到高端的Zig-Zig/Zag-Zag操作和Zig-Zag/Zag-Zig操作了（因为单纯的Zig和Zag不能pia扁一条链QAQ）。

可以非常非常清楚地看到，Zig-Zig/Zag-Zag操作可以把一条三个节点的链掰成反方向的链，而Zig-Zag/Zag-Zig操作甚至可以把一条折链变矮！于是我们写出了Splay的代码。
【分享一个小技巧：只需要讨论三个节点是否构成链就可以了，不需要傻乎乎地讨论到底是Zig还是Zag，妈妈再也不用担心我英语不好啦☆*:.?.o(≧▽≦)o.?.:*☆】

inline void Play(int u){//直接判定对u节点进行Zig或Zag操作 
	if(Ls[Fa[u]]==u)Zig(u);
	else Zag(u);
}
void Splay(int u,int e){//将u节点Splay到u成为e节点的子节点（e==0代表Splay到根节点） 
	Update(u);//u节点可能刚刚被修改过，不要忘记了呀 
	while(Fa[u]!=e){
		int v=Fa[u],w=Fa[v];
		if(w==e)Play(u);//只剩下一次操作了，不能再多操作了 
		else {
			if((Ls[v]==u)^(Ls[w]==v)){Play(u);Play(u);}//三点不构成直链，快用Zig-Zag/Zag-Zig来pia扁它 
			else {Play(v);Play(u);}//三点构成直链，快用Zig-Zig/Zag-Zag来扭曲它 
		}
	}
	if(e==0)rot=u;//不要忘记更新根节点了呀 
}

如果各位和我一样不懂均摊时间复杂度的分析，那就可以理解为通过Zig-Zig/Zag-Zag操作节点会把树尽量变得蜿蜒曲折,Zig-Zag/Zag-Zig操作则可以把蜿蜒曲折的道路变矮，最终使得整棵树相对平衡。但事实上，因为涉及到子树，情况要复杂得多【而我也没有能力讨论这些情况…>_<…】
有了pia扁树的保证，我们就可以放心大胆地实现操作了。

求第k大数的操作：
通过Size判断往左走还是往右走就可以啦，不要忘记节点自己也要算1个呀。

int Find_K(int k){ int p=rot; while(p){ if(k<=Sz[Ls[p]])p=Ls[p];//在左边 else if(k==Sz[Ls[p]]+1)break;//找到啦 else k-=Sz[Ls[p]]+1,p=Rs[p];//在右边 } return p; }

插入操作：
直接插入就行啦。

void Insert(int k){ if(tot++==0){//还没有插入根节点 Vl[tot]=k,Fa[tot]=0,rot=1; return; } int p=rot; while(p){//一定要找到合适的位置后才能插入哦 Sz[p]++; if(k<Vl[p]){ if(Ls[p])p=Ls[p];else {Ls[p]=tot;break;} } else { if(Rs[p])p=Rs[p];else {Rs[p]=tot;break;} } } Vl[tot]=k,Fa[tot]=p; Splay(tot,0);//不要忘了将新插入的节点Splay到根 }

删除操作：
先把要删除的节点Splay到根，然后咔嚓一声就把它删了，再把左子树里面最大的Splay到顶当根，然后直接把右子树连到根上就可以啦。

int Find(int k){ int p=rot; while(p){ if(k==Vl[p])break;//在左边 if(k<Vl[p])p=Ls[p];//找到啦 else p=Rs[p];//在右边 } return p; } bool Delete(int k){ int p=Find(k);//找到要删除的节点 if(!p)return 1;//骗纸！根本没有值为k的节点！ Splay(p,0); int l=Ls[p],r=Rs[p]; if(!l)rot=r,Fa[r]=0;//没有左子节点，直接让右子节点当根就行啦 else {//找到左子树中最大的节点 while(Rs[l])l=Rs[l]; Splay(l,p); rot=l;Fa[l]=0;Fa[r]=l;Rs[l]=r;//找到的节点当根，不要忘了把右子节点连上去 } Update(p);//记得更新Size return 0; }

全文完！
请用严肃的表情和语调大声朗读以下内容（不读标号）：
通过这篇博文，你应该学到：
1.SplayTree常数高，能跑能跳思维好。
2.Zig、Zag真奇妙，pia扁长链高变小。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!