successor和predecessor

来源：5-9 二分搜索树的顺序性

易萧

2017-06-13

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

然后我是这样想的：

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

写回答

1回答

liuyubobobo

2017-06-15

已采纳

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

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

加油！

liuyubobobo

易萧

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

2017-06-17

共3条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1