龍進Splay 规定：每访问一个节点后都要强制将其旋转到根节点。
这里面就分了三类情况来讨论：
1、如果x的父亲是根节点，直接将x左旋或右旋
2、如果x的父亲不是根节点，且x和父亲的儿子类型相同（也就是说，它们都是左子节点或都是右子节点），首先将其父亲左旋或右旋，然后将x右旋或左旋
3、如果x的父亲不是根节点，且x和父亲的儿子类型不同，将x左旋再右旋、或者右旋再左旋.
splay操作就是从被访问的节点x开始，递归地做上面的操作，直到x是根节点。并且，Splay之后，整棵树还是二叉搜索树。
插入操作
插入操作是一个比较复杂的过程，具体步骤如下（假设插入的值为x ）：
- 如果树空了，则直接插入根并退出。
- 如果当前节点的权值等于x，则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
- 否则按照二叉查找树的性质向下找，找到空节点就插入即可（然后进行Splay 操作）
删除操作
删除操作也是一个比较复杂的操作，具体步骤如下：
首先将x旋转到根的位置。
- 如果cnt[x]>0(x有不止一个 ），那么将cnt[x]减1并退出。
- 否则，合并它的左右两棵子树即可
查询x的排名
应用二叉搜索树的查找即可，只是最后要对找到的这个点进行Splay操作。
- 如果x比当前节点的权值小，向其左子树查找。
- 如果x比当前节点的权值大，将答案加上(左子树和当前节点)的大小，向其右子树查找。
- 如果x与当前节点的权值相同，将答案加1并返回
查询排名为x的数
设k为剩余排名，初始时，k=x
- 如果左子树大小小于k，则向左子树查找
- 否则，将k减去（左子树加上当前节点的大小）。若此时k≤0，那么就返回当前节点的权值。否则，然后向右子树查找。
在找到之后，要对那个节点进行Splay操作。
转载请注明来源：https://www.longjin666.cn/?p=1274
欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~
