主题

主题

 
   

Splay前驱与后继

  • 学Splay的时候不会,现在重新补回来。

接下来由于前驱与后继的相似性,只讨论前驱,后继类似。

  • 寻找已经存在的节点的前驱与后继是很简单的。

先讨论此问题。

  • 最简单的方法

找到当前节点,旋转到根。

如果有左子树,那么前驱是左子树中最大值。如果没有左子树,那么没有前驱。

时间复杂度O(2logn)。方便好写,常数相对有点大。

  • 另一种方法

同样先找到当前节点。

如果当前节点有左子树,就查找左子树中的最大值。如果没有左子树,那么往父亲节点寻找,找到第一个折点。

最后把前驱旋转到根。

例如下面这篇博客。蛮不错的。

http://blog.csdn.net/xjm199/article/details/20003045


  • 寻找不存在的节点的前驱与后继?

这样就不能先找到当前节点了。

假设我们定义前驱为最大的小于w的节点。我们现在讨论寻找前驱。

  • 较简单的方法

可以先插入这个节点,转换为已经存在的节点的前驱与后继。查找完之后再删除。

时间复杂度O(logn)。但是空间复杂度O(1)。

这个O(1)也不能小看。尤其是在树套树中,一次插入是O(1),那么意味着可能需要新增O(nlog^2n)的空间。且树套树的空间常数也是不能忽视的,常数为2与常数为3,就相当于200MB与300MB,就可能面临超空间的问题。

  • 另一种方法

有没有什么空间复杂度为O(0)的呢?

自己YY了一下。这也是做此笔记的最主要的原因。

每一个节点维护子树最小值minn与最大值maxn。那么边界条件就很简单了。如果minn>=w说明不存在小于w的节点,直接返回0即可。

接下来我们从根开始,如果当前节点data大于或者等于w,就跳到左儿子上。

这样做的效果:

  1. 如果根节点大于或者等于w,就会找到第一个小于w的节点(可能并不是最大的小于w的节点)。

  2. 如果根节点小于w,就直接停在根节点。

总之我们就是找到了一个小于w的节点,并且它的祖先都大于或者等于w,那么它的祖先的右子树自然都大于或者等于w的节点。它的左子树均比它小,自然不可能是最大的小于w的节点。

那么最大的小于w的节点,就限定在了当前节点以及其右子树中。

之后我们需要继续寻找。

  1. 如果当前节点的右子树的最小值小于w,那么最大的小于w的节点必然在当前节点的右子树。于是我们就跳到右子树上。

  2. 如果当前节点的右子树的最小值大于或者等于w,且当前节点data亦大于或者等于w,那么显然我们要跳到左儿子上。

  3. 否则我们就找到了最大的小于w的节点。

时间复杂度O(logn)。最后记得把前驱旋转到根。

  • 另一个拓展

考虑到我们的寻找的是最大的小于w的。事实上寻找最大的小于或者等于w的亦然。我们设计一个cmp函数即可。


代码如下:

https://code.csdn.net/snippets/2160189

 
 
评论