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

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注