在二叉搜索树中搜索一个数字。如果不存在，找比它小的最大数
Searching a number in a binary search tree. If it doesn't exist, find the the biggest number smaller than it
假设您有一个包含 n 个数的平衡二叉搜索树（例如 AVL 树）。
您需要一种算法来查找给定的数字 x，但如果找不到，
returns小于x的最大数
为了题目的缘故，不插入x然后删除它，解决方案应该是O(log(n))。
谢谢
这道题是关于寻找（虚拟）插入节点的中序前驱节点。我将首先解释什么是 Inorder Predecessor，然后解释我们如何在 BST 中找到 Inorder Predecessor。
在我们讨论中序前驱之前，我们必须首先熟悉二叉搜索树的中序遍历。
中序遍历是一种按照特定顺序访问二叉搜索树的所有节点的算法，如下面的递归算法所述：
Inorder(Node S)
Inorder(left child of S)
print S
Inorder(right child of S)
简单来说，我们递归打印左树，然后是中心节点，然后是右子树。
该算法非常简单而优雅，因为当它按此顺序打印键时，由于 BST 结构中键的排序，我们将得到一个特殊的键序列。那个特殊序列是什么？让我们跟踪 BST 的算法并检查一下。
让我们考虑如下所示的 BST：
在这里，让我们跟踪我们的算法，首先我们从根（值为20的节点）开始算法，然后按照算法的说法，我们递归地为左子树调用相同的函数，即以节点为根的子树8，我们再次调用 8 的左子树，即节点 4。此时 4 没有左子树，所以我们打印键 4。由于 4 没有右子树，我们完成了以 root 为根的子树4号节点，回溯到8号节点，现在打印8号节点，然后调用8号节点右子树的递归函数，按照算法一步步执行，打印出的序列为：4 , 8, 10, 12, 14, 20, 22
这是什么序列？这只是键的排序序列。
这是怎么发生的？好吧，这就是 BST 节点的结构方式：BST 有一个特殊的 属性，即对于每个节点 S，节点 S 左侧的所有键都小于 S，而 S 右侧的所有节点都是大于 S.
换句话说，中序遍历只是按照排序的顺序整齐地打印出二叉搜索树的键。
好的，现在我们了解了打印 BST 的中序遍历的递归算法，我们 re-focus 开始寻找比我们的目标节点小的最大节点的任务.这个节点是什么？它只是将在 BST 的中序遍历中我们虚拟插入的节点之前打印的节点。这称为 Inorder Predecessor。
让我们回顾一下 BST，了解什么是 Inorder Predecessor。
这里12的Inorder Predecessor是什么？我们做什么？我们知道一个节点的 Inorder Predecessor 是在 Inorder 遍历中打印这个节点之前打印的节点。这可能是哪个节点？要回答这个问题，我们必须可视化打印节点 12 的确切时间点。显然，对于通过我们的 Inorder 遍历算法在特定节点之前打印的内容，它应该是某个打印步骤已经完成的节点。在这种情况下，对于节点 12，我们看到在打印 12 之前紧接着调用递归打印 12 的左边 child。 12 的左边 child 是多少？它是 10。显然 10 是在 Inorder 遍历中将在 12 之前打印的节点。因此，10 是 12 的中序前身。
一般来说，很容易看出，如果一个节点有一个左子树，那么该节点的Inorder Precedessor就是它左子树中的最大节点。
但是如果节点没有左子树呢？比如说，节点 10 的 Inorder Predecessor 是什么？我们如何找到它？
好吧，这有点棘手，因为 10 没有左子树。让我们想想，哪个节点可以在节点 10 之前打印？我们正在寻找一个已经打印过的节点。首先，我们是如何到达遍历算法序列中的节点 10 的？我们是从节点 12 左边来的，Inorder Predecessor 会不会是 12？不，因为根据算法，节点 12 只会在 10 之后打印，因为 10 是通过对节点 12 的左子树的递归调用打印的。好吧，什么叫做 12？ 8 调用了对 12 的递归调用，作为对其右子树的递归调用的一部分。好的，8 可以是 Inorder Predecessor 吗？首先，我们已经打印了 8 了吗？是的，我们已经打印了 8，因为我们现在已经在 8 的右子树中了。 8 确实是在 Inorder Traversal 中节点 10 之前打印的节点。为什么？我们刚才做了什么？我们所做的只是回顾一下我们是如何在节点 10 结束的，追溯这些步骤并查看已经打印的第一个节点。显然，那是 Inorder 的前身。因此 8 是 10 的中序前身。
一般来说，很容易看出，如果一个节点没有左子树，你需要做的就是从你的节点上树到根节点，在这样做的过程中，找到右子树的节点child 的 parent，那么 parent 将是 Inorder Predecessor。
因此，要找到一个节点的中序前驱，您需要做的就是追溯遍历中如何到达该节点的递归调用。
总结：
如果节点有左子树，Inorder Predecessor 是节点左子树中的最大键。
别的
一直往上，直到找到一个 parent 的右 child 节点，那么 parent 就是 Inorder Predecessor.
现在，我们了解了什么是 Inorder Predecessor 以及如何在 BST 中找出它，让我们回到我们的任务。由于我们的节点首先不存在，那么我们将插入它（实际上至少），这意味着它在插入时将是一个叶子，这意味着它没有左子树，这意味着它的前任实际上只是向上那个树。因此，在一次遍历中，您应该能够完成此任务，而无需实际插入。
假设您有一个包含 n 个数的平衡二叉搜索树（例如 AVL 树）。
您需要一种算法来查找给定的数字 x，但如果找不到， returns小于x的最大数
为了题目的缘故，不插入x然后删除它，解决方案应该是O(log(n))。
谢谢
这道题是关于寻找（虚拟）插入节点的中序前驱节点。我将首先解释什么是 Inorder Predecessor，然后解释我们如何在 BST 中找到 Inorder Predecessor。
在我们讨论中序前驱之前，我们必须首先熟悉二叉搜索树的中序遍历。 中序遍历是一种按照特定顺序访问二叉搜索树的所有节点的算法，如下面的递归算法所述：
Inorder(Node S)
Inorder(left child of S)
print S
Inorder(right child of S)
简单来说，我们递归打印左树，然后是中心节点，然后是右子树。
该算法非常简单而优雅，因为当它按此顺序打印键时，由于 BST 结构中键的排序，我们将得到一个特殊的键序列。那个特殊序列是什么？让我们跟踪 BST 的算法并检查一下。
让我们考虑如下所示的 BST：
在这里，让我们跟踪我们的算法，首先我们从根（值为20的节点）开始算法，然后按照算法的说法，我们递归地为左子树调用相同的函数，即以节点为根的子树8，我们再次调用 8 的左子树，即节点 4。此时 4 没有左子树，所以我们打印键 4。由于 4 没有右子树，我们完成了以 root 为根的子树4号节点，回溯到8号节点，现在打印8号节点，然后调用8号节点右子树的递归函数，按照算法一步步执行，打印出的序列为：4 , 8, 10, 12, 14, 20, 22
这是什么序列？这只是键的排序序列。
这是怎么发生的？好吧，这就是 BST 节点的结构方式：BST 有一个特殊的 属性，即对于每个节点 S，节点 S 左侧的所有键都小于 S，而 S 右侧的所有节点都是大于 S.
换句话说，中序遍历只是按照排序的顺序整齐地打印出二叉搜索树的键。
好的，现在我们了解了打印 BST 的中序遍历的递归算法，我们 re-focus 开始寻找比我们的目标节点小的最大节点的任务.这个节点是什么？它只是将在 BST 的中序遍历中我们虚拟插入的节点之前打印的节点。这称为 Inorder Predecessor。
让我们回顾一下 BST，了解什么是 Inorder Predecessor。
这里12的Inorder Predecessor是什么？我们做什么？我们知道一个节点的 Inorder Predecessor 是在 Inorder 遍历中打印这个节点之前打印的节点。这可能是哪个节点？要回答这个问题，我们必须可视化打印节点 12 的确切时间点。显然，对于通过我们的 Inorder 遍历算法在特定节点之前打印的内容，它应该是某个打印步骤已经完成的节点。在这种情况下，对于节点 12，我们看到在打印 12 之前紧接着调用递归打印 12 的左边 child。 12 的左边 child 是多少？它是 10。显然 10 是在 Inorder 遍历中将在 12 之前打印的节点。因此，10 是 12 的中序前身。
一般来说，很容易看出，如果一个节点有一个左子树，那么该节点的Inorder Precedessor就是它左子树中的最大节点。
但是如果节点没有左子树呢？比如说，节点 10 的 Inorder Predecessor 是什么？我们如何找到它？
好吧，这有点棘手，因为 10 没有左子树。让我们想想，哪个节点可以在节点 10 之前打印？我们正在寻找一个已经打印过的节点。首先，我们是如何到达遍历算法序列中的节点 10 的？我们是从节点 12 左边来的，Inorder Predecessor 会不会是 12？不，因为根据算法，节点 12 只会在 10 之后打印，因为 10 是通过对节点 12 的左子树的递归调用打印的。好吧，什么叫做 12？ 8 调用了对 12 的递归调用，作为对其右子树的递归调用的一部分。好的，8 可以是 Inorder Predecessor 吗？首先，我们已经打印了 8 了吗？是的，我们已经打印了 8，因为我们现在已经在 8 的右子树中了。 8 确实是在 Inorder Traversal 中节点 10 之前打印的节点。为什么？我们刚才做了什么？我们所做的只是回顾一下我们是如何在节点 10 结束的，追溯这些步骤并查看已经打印的第一个节点。显然，那是 Inorder 的前身。因此 8 是 10 的中序前身。
一般来说，很容易看出，如果一个节点没有左子树，你需要做的就是从你的节点上树到根节点，在这样做的过程中，找到右子树的节点child 的 parent，那么 parent 将是 Inorder Predecessor。
因此，要找到一个节点的中序前驱，您需要做的就是追溯遍历中如何到达该节点的递归调用。
总结： 如果节点有左子树，Inorder Predecessor 是节点左子树中的最大键。 别的 一直往上，直到找到一个 parent 的右 child 节点，那么 parent 就是 Inorder Predecessor.
现在，我们了解了什么是 Inorder Predecessor 以及如何在 BST 中找出它，让我们回到我们的任务。由于我们的节点首先不存在，那么我们将插入它（实际上至少），这意味着它在插入时将是一个叶子，这意味着它没有左子树，这意味着它的前任实际上只是向上那个树。因此，在一次遍历中，您应该能够完成此任务，而无需实际插入。