二叉搜索树中KTH最小元素的最优求法

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (103)

我需要在二进制搜索树中找到KTH最小元素,而不需要使用任何静态/全局变量。如何有效地实现这一目标?我脑海中的解决方案是在O(N)中执行操作,这是最糟糕的情况,因为我计划对整个树进行无序遍历。但在内心深处,我觉得我并没有在这里使用BST的属性。我假设的解决方案是正确的,还是有更好的解决方案?

提问于
用户回答回答于

以下是这个想法的概要:

在BST中,节点的左子树T中存储的值小于T。如果k小于左侧子树中的元素数,则k最小元素必须属于左子树。否则,如果k是更大的,那么k最小的元素在右边的子树中。

我们可以扩大BST,使其中的每个节点在其左侧子树中存储元素数(假设给定节点的左子树包括该节点)。有了这段信息,就可以通过反复询问左侧子树中的元素数来遍历树,从而决定是对左子树还是右子树进行递归。

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

  1. 如果K=num_元素(T的左子树),那么我们要寻找的答案是节点中的值T
  2. 如果K>Num_元素(T的左子树),显然我们可以忽略左子树,因为这些元素也将小于k最小的。因此,我们将问题归结为找到k - num_elements(left subtree of T)右子树的最小元素。
  3. 如果K<num_元素(T的左子树),然后k最小值位于左子树中的某个位置,因此我们将问题简化为找到k左边子树中最小的元素。

复杂性分析:

这需要O(depth of node)时间,也就是O(log n)在最坏的情况下平衡BST,或O(log n)平均为随机BST。

BST要求O(n)存储,它需要另一个O(n)若要存储有关元素数量的信息,请执行以下操作。所有BST业务O(depth of node)时间,需要时间O(depth of node)额外的时间来维护“元素的数量”信息,以便插入、删除或旋转节点。因此,在左侧子树中存储有关元素数的信息将保持BST的空间和时间复杂性。

用户回答回答于

一个更简单的解决方案是执行无序遍历,并跟踪当前要打印的元素(而不是打印它)。当我们到达k时,打印元素并跳过树遍历的其余部分。

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

所属标签

可能回答问题的人

  • EatRice

    16 粉丝0 提问138 回答
  • 学生

    8 粉丝476 提问522 回答
  • 富有想象力的人

    5 粉丝0 提问344 回答
  • 最爱开车啦

    9 粉丝503 提问1.6K 回答

扫码关注云+社区

领取腾讯云代金券