BST 中给定键的中序前驱和后继

引言

二叉搜索树 (BST) 是计算机科学中广泛使用的一种强大数据结构，用于高效地执行搜索、插入和删除操作。在使用 BST 时，一项常见的任务是查找给定键的有序前驱和后继。

理解二叉搜索树 (BST)

在深入探讨有序前驱和后继之前，我们先简单回顾一下 BST 是什么。二叉搜索树是一种二叉树，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。BST 的关键特性是，对于任何节点，其左子树中的所有节点都具有小于其自身键的键，而其右子树中的所有节点都具有大于其自身键的键。此特性使搜索、插入和删除操作高效，对于平衡树通常具有 O(log n) 的时间复杂度。

中序遍历

中序遍历是一种按键的升序访问二叉树所有节点的方法。在 BST 中，中序遍历自然会按排序顺序给出元素。遍历顺序是：左子节点、根节点、右子节点。

有序前驱

BST 中一个节点的有序前驱是具有小于给定节点键的最大键的节点。换句话说，它是给定节点左子树中最右边的节点，或者是左子树中的最大元素。

有序后继

同样，BST 中一个节点的有序后继是具有大于给定节点键的最小键的节点。它是给定节点右子树中最左边的节点，或者是右子树中的最小元素。

图解

我们要找出键为 11 的节点的有序前驱和后继。

• 从根节点 (20) 开始。
• 向左遍历，因为 11 小于 20。
• 移动到 9。仍然，11 大于 9，所以向右移动。
• 到达 12。由于 11 小于 12，所以向左移动。
• 到达 11。现在，前驱是 9，后继是 12。

查找有序前驱和后继

要查找 BST 中给定键的有序前驱和后继，我们可以执行修改后的搜索操作。

• 搜索给定键：我们首先在 BST 中搜索给定键。如果找到键，则可以根据树的结构确定其有序前驱和后继。
• 如果键有左子树：如果与给定键对应的节点有左子树，则此子树中的最大元素将是有序前驱。
• 如果键有右子树：如果与给定键对应的节点有右子树，则此子树中的最小元素将是有序后继。
• 处理节点没有左子树或右子树的情况：如果与给定键对应的节点没有左子树或右子树，我们需要向上遍历树，直到找到一个其左子节点是给定节点祖先的节点。此节点将是有序前驱。同样，如果我们需要查找后继，我们向上遍历树，直到找到一个其右子节点是给定节点祖先的节点。此节点将是有序后继。

实施

说明

• 该程序定义了一个 TreeNode 结构来表示二叉树中的一个节点。每个节点都有一个整数值 (val) 以及指向其 left 和 right 子节点的指针。
• Solution 类包含一个 findPredecessorSuccessor 方法，负责查找 BST 中给定键的前驱和后继。
• findPredecessorSuccessor 方法接受 BST 的根节点、指向 pred 和 succ（将分别更新为指向前驱和后继）的引用，以及要查找其前驱和后继的键。
• 该方法递归遍历 BST。如果根节点为空，则函数返回。
• 如果根节点的值与 key 匹配，它将前驱设置为左子树中的最大值，并将后继设置为右子树中的最小值。
• 如果键小于当前根节点的值，则它会探索左子树。否则，它会探索右子树。
• 在 main 函数中，创建一个示例 BST。然后，调用 findPredecessorSuccessor 方法来查找给定键（本例中为 40）的前驱和后继。

程序输出

复杂度分析

在 BST 中查找有序前驱和后继的时间复杂度为 O(h)，其中 h 是树的高度。在最坏情况下，当树倾斜时，树的高度等于节点数，导致时间复杂度为 O(n)。但是，在平衡的 BST 中，高度为 O(log n)，从而实现高效操作。

结论

总之，该算法通过递归遍历高效地查找二叉搜索树 (BST) 中给定键的有序前驱和后继。它利用 BST 的结构，将前驱确定为左子树中的最大值，将后继确定为右子树中的最小值。其时间复杂度为 O(h)，其中 h 是树的高度，这表明它具有最佳性能，尤其是在平衡树中，使其成为各种 BST 应用程序的可靠解决方案。