logo标签列表

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

algorithmdata-structuresbinary-treebinary-search
116

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

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

8
这棵树是否平衡？ - kennytm
不是的。但如果它是平衡的，是否有最佳方式？ - bragboy
1
如果你在搜索“顺序统计量”一词，你会找到你需要的内容。 - RAL
我有点觉得下面大部分的答案虽然正确，但是它们都在作弊，因为它们使用了某种全局变量（无论是对整数的引用还是被递减并返回的变量）。如果绝对不允许使用这些变量，我会使用递归而不传入任何引用。 - Henley
35个回答
175
这里是大致的思路：
在二叉搜索树中，节点T的左子树只包含比节点T存储的值小的元素。如果k小于左子树中的元素数，则第k小的元素必须属于左子树。否则，如果k更大，则第k小的元素位于右子树中。
我们可以增强BST，使其每个节点都存储其左子树中的元素数（假定给定节点的左子树包括该节点）。有了这个信息，就可以通过反复询问左子树中的元素数来简单地遍历树，以决定是否递归到左侧或右侧子树。
现在，假设我们在节点T处：
1. 如果k == T的左子树中的元素数，则我们要找的答案是节点T中的值。 2. 如果k > T的左子树中的元素数，则显然我们可以忽略左子树，因为这些元素也比第k小的元素小。因此，我们将问题简化为查找右子树中第k - T左子树中元素数的最小元素。 3. 如果k < T的左子树中的元素数，则第k小的元素在左子树中某处，因此我们将问题简化为查找左子树中第k小的元素。
复杂度分析：
这需要O（节点深度）时间，在平衡的BST上最坏情况下为O（log n），在随机BST上平均为O（log n）。
BST需要O（n）存储空间，另外需要O（n）来存储有关元素数量的信息。所有BST操作都需要O（节点深度）时间，并且需要O（节点深度）额外时间来维护插入、删除或旋转节点的“元素数”信息。因此，存储左子树中元素数的信息可以保持BST的空间和时间复杂度。
59
要找到第N小的项目，只需要存储左子树的大小。如果您还想查找第N大的项目，则将使用右子树的大小。实际上，您可以使此过程更加经济：在根中存储整个树的总大小和左子树的大小。当您需要右子树的大小时，可以从总大小中减去左侧的大小。 - Jerry Coffin
37
这样的增强二叉搜索树被称为“顺序统计树”。 - Daniel
10
在第二步中，我认为“k - num_elements”应该改为“k - num_elements -1”，因为您需要包括根元素。 - understack
16
如果这棵树不包含一个字段来存储“其左右子树中元素数量的总和”，那么该方法最终的时间复杂度将为O（n），因为你需要在每个节点上走遍左或右子树以计算当前节点的k索引。 - Robert S. Barnes
1
@Nitin Garg：按照定义，二叉搜索树不允许有重复的值-请参见http://en.wikipedia.org/wiki/Binary_search_tree。 - nevets1219
显示剩余12条评论
67

更简单的解决方案是进行中序遍历并跟踪当前要打印的元素（但不要打印它）。当我们到达第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); 
}
1
+1：这个想法是朝着正确的方向发展，但可能需要解决一些细节问题；请参见https://dev59.com/WHE95IYBdhLWcg3wY9D6#23069077。 - Arun
1
我喜欢这个解决方案，因为BST已经有序，遍历应该就足够了。 - Merlin
3
如果n接近于这棵树的节点总数，你的算法将需要O(n)时间才能完成，这对于期望答案O(log n)来说很糟糕。 - Spark8006
13
public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

这是我基于上述算法在C#中实现的代码，我想发帖分享一下，让大家更好地理解。它对我很有效。

谢谢IVlad。

10
一种更简单的解决方案是进行中序遍历，并使用计数器 k 跟踪当前要打印的元素。当到达第 k 个元素时，将其打印出来。运行时间为 O(n)。请记住，函数的返回类型不能为 void，在每次递归调用后，它必须返回更新后的 k 值。更好的解决方案是使用增强型二叉搜索树，在每个节点上都有一个排序位置值。
public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}
我猜你的解决方案在空间复杂度方面比增强型二叉搜索树更好。 - zach
即使找到第k小的元素，搜索也不会停止。 - Vineeth Chitteti
10

//添加一个无需使用递归的Java版本

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}
我喜欢这个解决方案和相应的递归解决方案。老实说，对于这个问题的大多数答案都太令人困惑/复杂了，难以阅读。 - Henley
我喜欢这个解决方案！清晰而且很棒！ - Rugal
该解决方案按照“中序遍历”方式遍历树，在访问节点后递减计数器，直到计数器等于零时停止。最坏情况的时间复杂度为O(n)，与@IVlad的递归解决方案相比不是最优的，其最坏情况的时间复杂度为O(log n)。 - Jorge P.
7
4

使用计数器进行递归中序遍历

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

这个想法与@prasadvk的解决方案类似，但它有一些缺点（见下面的注释），因此我将其发布为一个单独的答案。
// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

注（与@prasadvk的解决方案不同之处）：

  1. 需要在三个位置进行if( counter == k )测试：（a）在左子树后，（b）在根节点后，以及（c）在右子树后。这是为了确保检测到所有位置的第k个元素，即无论它位于哪个子树中。

  2. 需要if( result == -1 )测试以确保仅打印结果元素，否则将打印从第k小的元素开始到根节点的所有元素。

该解决方案的时间复杂度为O(k + d)，其中d是树的最大深度。因此它使用了一个全局变量counter，但对于这个问题来说是不合法的。 - Valentin Shergin
嗨，Arun，你能举个例子解释一下吗？我不太理解你的第一个要点。 - Andy897
4

如果只有一个普通的二叉搜索树，你只能从最小值开始向上遍历，找到正确的节点。

如果你经常这样做，可以为每个节点添加一个属性，表示其左子树中有多少个节点。利用这一点，你可以直接下降到正确的节点。

3
对于非平衡搜索树，时间复杂度为O(n)。
对于平衡搜索树，在最坏情况下时间复杂度为O(k + log n)，但在分摊意义下只需O(k)。
每个节点都有一个额外的整数来表示子树的大小，则时间复杂度为O(log n)。这种平衡搜索树通常称为RankTree。
一般来说，还有一些不基于树的解决方案。
谢谢。
1

签名：

Node * find(Node* tree, int *n, int k);

调用方式：

*n = 0;
kthNode = find(root, n, k);

定义：

Node * find ( Node * tree, int *n, int k)
{
   Node *temp = NULL;

   if (tree->left && *n<k)
      temp = find(tree->left, n, k);

   *n++;

   if(*n==k)
      temp = root;

   if (tree->right && *n<k)
      temp = find(tree->right, n, k);

   return temp;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接