NEW Rotate
void Rotate(int x){ //代码不变 int y=ff[x],z=ff[y],k=(ch[y][1]==x); ch[z][ch[z][1]==y]=x; ff[x]=z; ch[y][k]=ch[x][k^1]; ff[ch[x][k^1]]=y; ch[x][k^1]=y; ff[y]=x; //只有节点x,y的大小发生了变化（看图） update(y),update(x); } 前驱/后驱前驱：比x小的最大节点；后驱：比x大的最小节点
先找到该节点，根据BST性质，其前驱即其左子树最右边的节点（进入其左儿子之后一直向右转），其后驱即其右子树最左边的节点（进入其右儿子之后一直向左转）
前驱 inline int pre(int x){ find(x); //查找后，此时树根即为查询节点 int u=ch[rot][0]; //进入左子树 if(u==0) return -1; // 没有比x小的数 while(ch[u][1]!=0) u=ch[u][1]; //一路向右 return u; } 后驱 inline int nxt(int x){ find(x); //查找后，此时树根即为查询节点 int u=ch[rot][1]; //进入右子树 if(u==0) return -1; // 没有比x大的数 while(ch[u][0]!=0) u=ch[u][0]; //一路向左 return u; } 删除根据前驱后驱的性质可得
\[
MIN,\cdots,pre(x),x,nxt(x),\cdots,MAX
\]
（即同时满足\(pre(x) < x < nxt(x)\)的x只有一个）那么我们可以根据这个性质x这一个节点夹逼到某个确定的位置，然后干净地干掉（无需维护其他信息）
具体先将x的前驱旋至树根，再旋转x的后驱，使x的后驱成为树根的儿子，这时我们会发现x被夹逼到树根的右儿子的左儿子（或者后驱节点的左儿子）
inline void delete(int x){ int xp=pre(x),xn=nxt(x); splay(xp, 0); //将x的前驱旋至树根 splay(xn, rot); //旋转x的后驱，使x的后驱成为树根的儿子 int u=ch[xn][0]; //即将被删除的节点 if(cnt[u]>1){ //如果不止一个节点 cnt[u]--; //那么将其个数减一即可 splay(u,0); //记得Splay！ }else ch[xn][0]=0; //干净地干掉 } 第k大 inline int findk(int x){ int u=rot; if(size[u]<x) return -1; //不存在 while(1){ if(x<=size[ch[u][0]]+cnt[u]) u=ch[u][0]; //如果左子树大小加节点副本数(cnt)大于x，那么第k大一定在左子树中，进入左子树 else if(x==size[ch[u][0]]+cnt[u]) return u; //如果左子树大小加节点副本数(cnt)恰等于x，那么第k大就是当前节点 else u=ch[u][1], x-=size[ch[u][0]]+cnt[u]; //如果左子树大小加节点副本数(cnt)小于x，那么第k大一定在右子树中，进入左子树，但是要同时减去左子树的个数 } } 参考个人觉得写的很好的博客：
[Splay入门解析【保证让你看不懂（滑稽）】](https://www.cnblogs.com/cjyyb/p/7499020.html)
Splay入门详解
More Senior Data Structure · 特别浅地浅谈Splay
本文采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载，请注明出处： 转载自：Santiego的博客