以Optimum方式在二叉搜索树中查找第k个最小元素

Question

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

Answer 1

这里只是一个概念的概述:

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

我们可以扩充BST以使其中的每个节点存储其左子树中的元素数量(假设给定节点的左子树包括该节点).通过这条信息,通过反复询问左子树中的元素数量来遍历树是很简单的,以决定是否递归到左子树或右子树.

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

1. 如果k == num_elements(T的左子树),那么我们要寻找的答案就是节点中的值T.
2. 如果k> num_elements(T的左子树),那么显然我们可以忽略左子树,因为那些元素也将小于k最小的子树.因此,我们将问题减少到找到k - num_elements(left subtree of T)正确子树的最小元素.
3. 如果k <num_elements(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的空间和时间复杂度.

Answer 2

一个更简单的解决方案是进行顺序遍历并跟踪当前要打印的元素(不打印它).当我们到达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); 
}

Answer 3

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

Answer 4

更简单的解决方案是进行顺序遍历并使用计数器k跟踪当前要打印的元素.当我们到达k时,打印元素.运行时为O(n).记住函数返回类型不能为void,它必须在每次递归调用后返回其更新的k值.对此更好的解决方案是增强的BST,在每个节点处具有排序的位置值.

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;
}

Answer 5

//添加没有递归的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();
        }
    }
}

Answer 6

您可以使用迭代顺序遍历:http: //en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal ,在将节点弹出堆栈后,可以简单地检查第k个元素.