Splay入门

Splay入门 BST与Splay

二叉查找树(BST)，保证任意节点的左儿子小于其父亲，任意节点的右儿子大于其父亲的二叉树。但是当出现毒瘤数据时，BST会退化为链，从而影响效率。而Splay是其中的一种比较万能的填坑方法。

Rotate

Splay基本旋转操作。在不破坏二叉查找树(BST)结构的前提下，将一个节点向上旋转一层，使其曾经的父亲成为他现在的儿子（图中x节点）

这种旋转模式可以找出普遍规律的，这里不多阐述，引用一下yyb神犇总结的

1.X变到原来Y的位置
2.Y变成了 X原来在Y的 相对的那个儿子
3.Y的非X的儿子不变 X的 X原来在Y的 那个儿子不变
4.X的 X原来在Y的 相对的 那个儿子 变成了 Y原来是X的那个儿子

请结合图和代码理解一下

void Rotate(int x){//旋转节点x //k表示x是否为y的右节点；y即图中y节点，x即图中x节点，z即图中A节点 int y=ff[x],z=ff[y],k=(ch[y][1]==x); //将x与y位置互换，并更新其父亲 ch[z][ch[z][1]==y]=x; ff[x]=z; //将图中D节点从x的右儿子变为y的左二子，k^1表示0,1取反（0^1=1,1^1=0） ch[y][k]=ch[x][k^1]; ff[ch[x][k^1]]=y; //将y更新 ch[x][k^1]=y; ff[y]=x; } /* ff[x]表示x的父亲 ch[x][1]表示x的右节点 ch[x][0]表示x的左节点 1^1=0 1^0=1 */

这样，每次有新节点加入、删除或查询时，都将其旋转至根节点，这样可以保持BST的平衡。

Splay为什么能让BST保持平衡的玄学原理很多博客未提及。自己yy了一天，搞出了个理由，表述不严谨，意会一下。粗略证明：对于随机生成的数据，裸BST本来就可以平衡，而Splay这种旋转行为的本身对于数据也是随机性的，所以最后还是可以平衡；对于毒瘤单调递增或递减的数据，裸BST不能平衡，效率低的原因可以看做是因为树退化成链，也可以看做是因为每一个新节点在插入时都需要比较一些严重脱离当前插入数据范围（趋势）的数据（如插入1,2,3……10，1000,1001,1002……1010时，每次插入大于等于1000的数时，裸BST每次都要先和前10个比较大小，但是其实这是不必要的，因为前10个数远小于插入的数，如果像这样每次都要访问这些低频节点，会大大增加其复杂度），而每次的Splay操作就是使根节点尽量符合当前插入数据的趋势，避免冗余的比较，让那些低频节点访问次数降低。证毕

Splay

然而单纯的Rotate操作还是不够，有些情况需要考虑，同上，记y为当前需要旋转的节点x的父亲，z为y的父亲（也是x的祖父），\(k(x,y)\)表示节点x,y的关系（x为y的右儿子还是为y的左儿子），特别的，当\(k(x,y)=k(y,z)\)（或者即x,y,z三点共线）时，两次单旋对于复杂度没有优化，如图：

我们必须要先将其父节点向上旋转一次，再将要旋转的节点向上旋转一次，如图：

其他情况则直接做两次旋转即可

inline void splay(int x, int goal){ //将x旋转直至成为goal的儿子 while(ff[x]!=goal){ int y=ff[x],z=ff[y]; if(z!=goal) //如果y已经是根节点的儿子了，那么只需要将x向上旋转一次就好了，不需要两次旋转 ((ch[z][0]==y)^(ch[y][0]==x))?rotate(x):rotate(y); //x,y,z三点共线是否三点一线 rotate(x);//再旋转一下 } if(goal==0) rot=x; //更新树根（0是树根的父亲） } 查找操作

非递归，比较简单，查找后，平衡树的根(rot)就是查找到的节点

/* rot维护了这棵平衡树的树根 val[x]获取节点x的值 */ inline void find(int x){ int u=rot; //rot为树根 if(u==0) return; //树空 while(ch[u][x>val[u]]!=0&&x!=val[u]) //节点存在（即不为0）并且不是x，才进入到下一层 u=ch[u][x>val[u]]; //进入到相应的子树中 splay(u,0); //每次查询都要将节点旋转至树根，原理前文已提 } 插入 inline void insert(int x){ int fa=0,u=rot; while(u!=0&&x!=val[u]){ fa=u; u=ch[u][x>val[u]]; } if(u!=0) //x存在 cnt[u]++; //已有x，那么增加其个数 else{ //没有x存在 u=tot++; //分配一个新的节点编号 if(fa==0) //新建一个树根 rot=u; //更新树根 else //新建叶节点 ch[fa][x>val[fa]]=u; //更新其父亲的信息 //维护节点的其他信息 val[u]=x; ff[u]=fa; cnt[u]=1; size[u]=1; //ch[u][0]=ch[u][1]=0; } splay(u,0); } Update

根据Splay自底向上旋转的性质，根据左右儿子的节点大小(size)以维护当前节点大小（用于求第k小问题）

void update(int x){ size[x]=size[ch[x][0]]+sizep[ch[x][1]]; //左右儿子 }

每次Rotate改变树形状时调用