c++ - 如何定位具有 O(log n) 时间复杂度的直接前驱

Question

首先，我想让任何人知道这是一项任务，我已经用 O(n) 完成了定位直接前导，但我想用 O(log n) 来完成，我知道这是可能的，因为树是 AVL 树。

我用 O(n) 完成它的方法是我根据键(记录)将树分成 2 并对左树进行最大搜索，对右树进行最小搜索。我知道它不是 log n，因为在我缩小了解决方案之后，我仍然必须处理左树或右树中的所有节点，所以充其量它仍然是 1/2n。

我可以看到解决方案的模式，但仍然无法全神贯注。我正在考虑使用根和节点指针，但我仍然不确定如何实现它。

如有任何指点，我将不胜感激，我已经用谷歌搜索并尝试解决这个问题好几天了，但无济于事。

Answer 1

给定一个 AVL 树中的节点 N，存在三种情况:

1. N 有一个左 child L。那么 N 的直接前驱必须是 L 最右最深的后代。要找到它，您需要下降到 L 的子树，在每个子树上取右分支子节点。最多可以有 log n 个级别，所以这是 O(log n)。

2. N 没有左 child ，但它本身是父 P 的右 child 。那么 P 必须是直接前驱，位于 O(1) 时间。

3. N没有左 child ，是一个父P的左 child 。然后沿着树向根走，直到找到一个节点是一个上升的A的右 child 。如果没有这样的A , N 没有任何前驱；否则 A 是 N 的直接前导。同样，最多可以检查 log n 个父级别，所以这也是 O(log n)。

确定三个应用中的哪一个应用显然可以在 O(1) 时间内完成，因此总时间复杂度为 O(log n)。

AVL 树示例供引用(这与 Wikipedia page for AVL tree 中给出的示例相同，但我重新创建了图形而不是复制图像；如果有人想制作，可以从 here 中 fork 源修改):

节点 17 和 50 是情况 1 的示例；节点 76 是情况 2 的示例；节点 9 是情况 3 的示例，没有前导；节点 19 是案例 3 的示例。如果您通过查看上面树中的示例来思考每个案例，您将能够确认这些陈述是正确的。这可能比通过正式证明(仍然可以给出)更容易。