algorithm - 在平衡二叉搜索树中查找键的后继时遇到问题

Question

正如问题所述，我正在尝试找到一种算法来找到平衡二叉搜索树中关键“k”的后继。我认为平衡的 BST 与 AVL 树相同（如果我错了，请纠正我）。我希望我能在 O(log n) 时间内一次性完成此操作，但我发现的所有内容都表明我需要先从树的右侧向下，然后从左侧向下。我对整棵树都是新手，但仍然觉得它有点混乱。任何帮助将不胜感激！

谢谢。

Answer 1

In a binary search tree, you have two path option to go down : left or right. Now suppose we have an element k in a node N. We want to find k's successor, which is the smallest element of the tree which is greater than k.

There are 3 use cases here :

• N has a non-NULL right child : the leftmost element of the right subtree is k's successor.
• N has not such right child and is the left child of its parent P. In this case, P holds the successor of k.
• Finally, N is the right child of its parent P. Then, to find its successor you must follow a more elaborate procedure shown below ...

Starting from S = Parent(P) : while S ≠ Root AND P ≠ Left(S)

1. P ← S
2. S ← Parent(S)

If S = Root and P = Right(S), then k was the maximum element of the tree ... Otherwise, just perform the following loop after setting S ← Right(S):

While S ≠ NULL :

1. P ← S
2. S ← Left(S)

When this loop ends, P holds k's successor.

Answer 2

If the node with key k has a right subtree, it is the leftmost node in that subtree. Otherwise, if the node with key k is a left child it is the parent of this node. Otherwise, find the closest ancestor of the node other than its immediate parent that has a right subtree it is the leftmost node in that subtree. If no such ancestor exists, the node was the maximum and does not have a successor.

Since the tree is balanced, you can always find it in O(log n).