我需要在不使用任何静态/全局变量的情况下找到二叉搜索树中第 k 个最小的元素。如何高效实现? 我想到的解决方案是在 O(n) 中执行操作,这是最坏的情况,因为我打算对整棵树进行中序遍历。但在内心深处,我觉得我在这里没有使用 BST 属性。我的假设解决方案是否正确,或者是否有更好的解决方案可用?
最佳答案
这里只是一个想法的大纲:
在 BST 中,节点 T
的左子树仅包含小于存储在 T
中的值的元素。如果 k
小于左子树中的元素数,则第 k
最小的元素必须属于左子树。否则,如果 k
较大,则第 k
最小的元素在右子树中。
我们可以扩充 BST,让其中的每个节点存储其左子树中元素的数量(假设给定节点的左子树包含该节点)。有了这条信息,遍历树就很简单了,反复询问左子树的元素个数,决定递归到左子树还是右子树。
现在,假设我们在节点 T:
- 如果 k == num_elements(T 的左子树),那么我们要寻找的答案就是节点
T
中的值。 - 如果 k > num_elements(T 的左子树),那么显然我们可以忽略左子树,因为这些元素也将小于第
k
个最小的元素。因此,我们将问题简化为找到k - num_elements(T 的左子树)
右子树的最小元素。 - 如果 k < num_elements(T 的左子树),则第
k
最小的元素位于左子树中的某处,因此我们将问题简化为寻找k
左子树中的第 k 个最小元素。
复杂度分析:
这需要 O(depth of node)
时间,在平衡 BST 上最坏的情况下是 O(log n)
,或者 O(log n)
随机 BST 的平均值。
一个 BST 需要 O(n)
的存储,而它需要另一个 O(n)
来存储关于元素数量的信息。所有BST操作都需要O(depth of node)
时间,插入、删除需要O(depth of node)
额外的时间来维护“元素个数”信息或节点的旋转。因此,在左子树中存储有关元素数量的信息保持了 BST 的空间和时间复杂度。
关于algorithm - 以最佳方式在二叉搜索树中找到第 k 个最小元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2329171/