搜索 BST 的递归函数的 space 复杂度是多少？ - O(h) 或 O(log(n))？
What is the space complexity of a recursive function that searches a BST? - O(h) or O(log(n))?
所以我为 BST 写了一些代码，我正在寻找其中是否包含 target node。
每 recursive call，树的一半得到 'eliminated'，即我们将需要的节点数减少到 search for in half。现在虽然我知道这等于 O(log(n)) space，但它不也等于树的高度 O(h) 吗？
作为一个可视化的例子，请看下面：
假设我们要在我们的 BST 中寻找 14，递归调用的最多次数将等于树的高度，3？这个对吗？我想这也适用于一般情况吗？因为我想不出这不是真的例子。
在 BST 中，仅当树完全平衡时，h 对应于 log(n)，而通常您的搜索将是 O(h)。
以一棵完全向一侧倾斜的树为例，如下所示：
此处树的高度为 7，最坏的情况是您将在何处搜索最后一个节点，在树中执行 7 个步骤，因此没有 log(n) 复杂性。
所以我为 BST 写了一些代码，我正在寻找其中是否包含 target node。
每 recursive call，树的一半得到 'eliminated'，即我们将需要的节点数减少到 search for in half。现在虽然我知道这等于 O(log(n)) space，但它不也等于树的高度 O(h) 吗？
作为一个可视化的例子，请看下面：
假设我们要在我们的 BST 中寻找 14，递归调用的最多次数将等于树的高度，3？这个对吗？我想这也适用于一般情况吗？因为我想不出这不是真的例子。
在 BST 中，仅当树完全平衡时，h 对应于 log(n)，而通常您的搜索将是 O(h)。
以一棵完全向一侧倾斜的树为例，如下所示：
此处树的高度为 7，最坏的情况是您将在何处搜索最后一个节点，在树中执行 7 个步骤，因此没有 log(n) 复杂性。