二叉搜索树的splay操作

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