logo标签列表

在最优方式中查找二叉搜索树中第k小的元素

algorithmdata-structuresbinary-treebinary-search
116

我需要在二叉搜索树中找到第k个最小的元素，且不能使用任何静态/全局变量。如何高效实现？

我目前考虑的解决方案是，最坏情况下通过遍历整棵树进行O(n)操作。但我感觉这里没有充分利用二叉搜索树的性质。请问我的解决方案是否正确，还有更好的方案吗？

8
这棵树是否平衡？ - kennytm
不是的。但如果它是平衡的，是否有最佳方式？ - bragboy
1
如果你在搜索“顺序统计量”一词，你会找到你需要的内容。 - RAL
我有点觉得下面大部分的答案虽然正确，但是它们都在作弊，因为它们使用了某种全局变量（无论是对整数的引用还是被递减并返回的变量）。如果绝对不允许使用这些变量，我会使用递归而不传入任何引用。 - Henley
35个回答
-1

我写了一个整洁的函数来计算第k小的元素。它使用中序遍历，并在到达第k小元素时停止。

void btree::kthSmallest(node* temp, int& k){
if( temp!= NULL)   {
 kthSmallest(temp->left,k);       
 if(k >0)
 {
     if(k==1)
    {
      cout<<temp->value<<endl;
      return;
    }

    k--;
 }

 kthSmallest(temp->right,k);  }}
没有提供任何指标说明为什么这是最优的。在大型和小型情况下都是如此。 - Woot4Moo
-1
 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    }

这个Java递归算法，一旦找到第k小的元素，便停止递归。

-2
int RecPrintKSmallest(Node_ptr head,int k){
  if(head!=NULL){
    k=RecPrintKSmallest(head->left,k);
    if(k>0){
      printf("%c ",head->Node_key.key);
      k--;
    }
    k=RecPrintKSmallest(head->right,k);
  }
  return k;
}
3
请始终附带一定程度的描述来说明代码的作用以及它如何有助于解决问题。 - Ren
-2
public TreeNode findKthElement(TreeNode root, int k){
    if((k==numberElement(root.left)+1)){
        return root;
    }
    else if(k>numberElement(root.left)+1){
        findKthElement(root.right,k-numberElement(root.left)-1);
    }
    else{
        findKthElement(root.left, k);
    }
}

public int numberElement(TreeNode node){
    if(node==null){
        return 0;
    }
    else{
        return numberElement(node.left) + numberElement(node.right) + 1;
    }
}
-5

对于二叉搜索树，中序遍历将按顺序返回元素...

只需执行中序遍历并在遍历k个元素后停止。

当k为常数时，时间复杂度为O(1)。

3
说某个算法在“k为常数时是O(1)”有点像作弊。我可以用这种说法来说任何算法都是O(1)... - IVlad
4
请问...它怎么可能独立于树的大小？试着找到最小的元素...那是O(1)吗？那么如何可能以O(1)的时间复杂度找到第k小的元素呢？ - RAL
@Anon：是的，这使得预计算结果为O(N)，使用中序遍历回答查询为O(1)。无论如何，我的观点是假设k是常数是没有根据的假设，因为问题没有说明。 - IVlad
对Robert的评论点赞。即使在平衡树中查找最小值（k=1）也是O(log n)。（并且回答的人点踩）。 - Aryabhatta
-1 是因为答案误导人（对于二叉搜索树来说，它的时间复杂度不是O(1)，而是O(N)；对于平衡树来说，它的时间复杂度是O(log N)）。 - kgadek
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接