algorithm - 以最佳方式在二叉搜索树中找到第 k 个最小元素

标签 algorithm data-structures binary-tree binary-search

我需要在不使用任何静态/全局变量的情况下找到二叉搜索树中第 k 个最小的元素。如何高效实现? 我想到的解决方案是在 O(n) 中执行操作,这是最坏的情况,因为我打算对整棵树进行中序遍历。但在内心深处,我觉得我在这里没有使用 BST 属性。我的假设解决方案是否正确,或者是否有更好的解决方案可用?

最佳答案

这里只是一个想法的大纲:

在 BST 中,节点 T 的左子树仅包含小于存储在 T 中的值的元素。如果 k 小于左子树中的元素数,则第 k 最小的元素必须属于左子树。否则,如果 k 较大,则第 k 最小的元素在右子树中。

我们可以扩充 BST,让其中的每个节点存储其左子树中元素的数量(假设给定节点的左子树包含该节点)。有了这条信息,遍历树就很简单了,反复询问左子树的元素个数,决定递归到左子树还是右子树。

现在,假设我们在节点 T:

  1. 如果 k == num_elements(T 的左子树),那么我们要寻找的答案就是节点 T 中的值。
  2. 如果 k > num_elements(T 的左子树),那么显然我们可以忽略左子树,因为这些元素也将小于第 k 个最小的元素。因此,我们将问题简化为找到 k - num_elements(T 的左子树) 右子树的最小元素。
  3. 如果 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/

相关文章:

c++ - 计算二叉搜索树的高度

java - PrintWriter 类未按预期工作

string - 如何确定字符串的最小公约数?

algorithm - 绘制别名、像素完美的 1px 样条曲线(特别是 Catmull-Rom)

algorithm - 如何递归解决移动受限的汉诺塔?

swift - 访问结构属性

c - 有序链表的链表

c - SYNC13C SPOJ 错误答案

algorithm - 如何在二叉搜索树中设置下界?

data-structures - 跳过列表——用过它们吗?