performance - 在给定的平衡二叉搜索树中查找最小(或最大)k 个元素

Question

给定一个具有整数节点的平衡二叉搜索树，我需要编写一个算法来找到最小的 k 个元素并将它们存储在链表或数组中。棘手的部分是，要求这种算法在 O(k+log(n)) 中运行，其中 n 是树中元素的数量。我只有一个运行 O(k*log(n)) 的算法，它使用等级函数。所以我的问题是如何实现所需的性能？

我已经编写了一个代码来执行这种算法，但我不知道它是否以 O(k+log(n)) 的速度运行:

(大小函数是给定子树的节点数。)

// find k smallest elements in the tree
public Iterable<Key> kSmallest(int k) {
    LinkedList<Key> keys = new LinkedList<Key>();
    kSmallest(k, root, keys);
    return keys;
}

// find k smallest elements in the subtree given by node and add them to keys
private void kSmallest(int k, Node node, LinkedList<Key> keys) {
    if (k <= 0 || node == null) return;
    if (node.left != null) {
        if (size(node.left) >= k) kSmallest(k, node.left, keys);
        else {
            keys.add(node.key);
            kSmallest(k - 1, node.left, keys);
            kSmallest(k - 1 - size(node.left), node.right, keys);
        }
    }
    else {
        keys.add(node.key);
        kSmallest(k - 1, node.right, keys);
    }
}

Answer 1

只需要中序遍历并在遍历 k 个节点时停止。这将在 O(k+log(n)) 时间内运行。

代码:

int k = nodesRequired;
int A[] = new int[k];
int number_of_nodes=0;
void traverse_tree(tree *l){
    if (number_of_nodes<k) {
        traverse_tree(l->left);
        process_item(l->item);
        traverse_tree(l->right);
    }
 }

 void process_item(item){
     A.push(item);
     ++number_of_nodes;
 }