successor和predecessor

Question

本来我是在考虑floor和ceil的，你说没有一个具体的键值可供查找前驱和后继，我在想，临时执行一个插入操作不就可以了。但是，它没有左右子节点啊，那么前面讲的节点删除只在至少有一个节点的时候才能直接找到前驱和后继，但如果它没有左右节点呢，岂不是还是要和floor和ceil一样的考虑。

然后我是这样想的：

假设这个叶节点为p，如果它位于父节点的左节点，那么它沿右上角方向回去的遇到某一个节点是父节点的右节点，那么p就是这个祖父节点的后继，反过来，这个祖父节点就是p的前驱，找p的后继是相反的。问题是又怎么知道判断的节点是父节点的哪个节点

Answer 1

liuyubobobo 2017-06-15 01:58:22

临时插入键值的思想很有意思。这样就把floor和ceil的问题转换成了寻找这个节点的前驱和后继。可以试试看：）

至于寻找前驱和后继，我们在Hubbard Deletion中，删除一个节点，就要寻找这个删除节点的后继啊，请再仔细体会一下这个过程：）

对于floor和ceil的实现，我在这个课程的官方github中提供了一个递归版本的实现，供参考：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil

加油！

• 提问者 易萧 #1

  非常感谢！

• 提问者 易萧 #2

  那个递归算法把和自己相同的值看成自己的floor和ceil啊？不应该寻找其它的么。
  官方的floor和ceil我看懂了，但它是从根开始查找，而删除节点是从这个节点开始搜索左右子树的，如果没有了任何一边的子树，都不需要去找前驱或者后继了，如果它就是叶节点，直接删除就好了。

• liuyubobobo 回复 提问者 易萧 #3

  floor和ceil就是这样定义的哦，对于已经存在的元素，floor和ceil就是他自己，本质上是“大于等于x的最小值”和“小于等于x的最大值”。当然，你可以根据自己的逻辑需要，取寻找“大于x的最小值”和“小于x的最小值”。