splay_tree伸展树
伸展树(Splay Tree)是二叉检索树的改进。 对伸展树的操作的平摊复杂度是O(log2n)。 伸展树的空间要求、编程难度非常低。
注意splay伸展树一定要时刻保证它的二叉检索性!
伸展树与二叉查找树一样，也具有有序性。
即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。
伸展树可以自我调整，这就要依靠
伸展操作splay(x)了！！！
伸展操作Splay(x)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树中的元素x调整至树的根部的操作。
在旋转的过程中，要分三种情况分别处理：
1)Zig 或 Zag
2)Zig-Zig 或 Zag-Zag
3)Zig-Zag 或 Zag-Zig
我看有些大犇的blog上直接用的rotate操作，它和splay操作本质上是一样的，不过我个人觉得splay要比rotate好想一些，也要好懂一些。
关于zig和zag的故事，我就不赘述了。
splay可以干什么？！
查找 find
插入 insert
删除 del
求最大值 get_max
求最小值 get_min
求前趋 get_pre
求后继 get_suc
求第k大 get_kth_max
求第k小get_kth_min
合并 merge
and so on......
然而.......
伸展操作是基础！
伸展操作是基础！
伸展操作是基础！
好了，废话不多说，直接上code！
#include<bits/stdc++.h> const int maxn=/**/; int ls[maxn],rs[maxn],fa[maxn],_size[maxn],val[maxn]; int n,m,x,cnt=0,delta=0;char cmd; int tot=0,root=0; 左旋/// void zig(int x){ int y=fa[x],z=fa[y]; if(ls[z]==y)ls[z]=x; else rs[z]=x; fa[x]=z; ls[y]=rs[x]; fa[rs[x]]=y; rs[x]=y; fa[y]=x; _size[x]=_size[y]; _size[y]=_size[ls[y]]+_size[rs[y]]+1; } 右旋 void zag(int x){ int y=fa[x],z=fa[y]; if(ls[z]==y)ls[z]=x; else rs[z]=x; fa[x]=z; rs[y]=ls[x]; fa[ls[x]]=y; ls[x]=y; fa[y]=x; _size[x]=_size[y]; _size[y]=_size[ls[y]]+_size[rs[y]]+1; } ///伸展操作 void splay(int x){ int y,z; while(fa[x]) { y=fa[x]; z=fa[y]; if(z) { if(ls[z]==y) { if(ls[y]==x)zig(y),zig(x); else zag(x),zig(x); } else { if(rs[y]==x)zag(y),zag(x); else zig(x),zag(x); } } else { if(ls[y]==x)zig(x); else zag(x); } } root=x; } 查询操作/// int find(int key){ int p=root; while(p) { if(key==val[p])break; if(key<val[p])p=ls[p]; else p=rs[p]; } return p; } //插入操作 void insert(int key){ if(!tot) { val[++tot]=key; fa[tot]=0; _size[tot]=1; root=tot; return; } tot++; int p=root; while(p) { _size[p]++; if(key<val[p]) { if(ls[p])p=ls[p]; else {ls[p]=tot;break;} } else { if(rs[p])p=rs[p]; else {rs[p]=tot;break;} } } val[tot]=key; fa[tot]=p; _size[tot]=1; splay(tot);//维护平衡树 } ///找最大 int get_max(int k){ int p=k; while(rs[p])p=rs[p]; return p; } ///找最小 int get_min(int k){ int p=k; while(ls[p])p=ls[p]; return p; } ///求后继/ int get_pre(int x){ splay(x); return get_max(ls[x]); } ///求前驱/ int get_suc(int x){ splay(x); return get_min(rs[x]); } ///删除操作// void del(int key){ int p=find(key); if(p) { splay(p); int left_son=ls[p],right_son=rs[p]; fa[left_son]=ls[p]=rs[p]=fa[right_son]=0; if(!left_son)root=right_son,fa[right_son]=0; else { root=left_son; left_son=get_max(left_son); splay(left_son); fa[left_son]=0; fa[right_son]=left_son; rs[left_son]=right_son; } _size[root]+=_size[rs[root]]; } } //求第k小/ int get_kth_min(int k){ int p=root; while(p) { if(_size[ls[p]]+1==k)break; if(k<=_size[ls[p]])p=ls[p]; else { k-=_size[ls[p]]+1; p=rs[p]; } } splay(p); return p; } //求第k大/// int get_kth_max(int k){ int p=root; while(p) { if(_size[rs[p]]+1==k)break; if(k<=_size[rs[p]])p=rs[p]; else { k-=_size[rs[p]]+1; p=ls[p]; } } splay(p); return p; } /// // // // // // 前方高能！！！ // // // // // /// int main(int argc,const char*argv[]) { //write your code }
