选择第i个最小数量的分隔数字序列的最佳方法

Question

如果我给了一组特定的数字(我将它存储在平衡的二进制搜索树中以方便),那么我想回答一个查询,要求我告知[A,B]之间的第i个最小数字是什么是一个执行该任务的快速算法？

从技术上讲,我可以从根遍历搜索A的树(或者一个数字,如果A不存在则立即大于该数字),而不是回溯搜索B(或小于B的数字),并且在这样做时我可以保留一个计数器我,确定我什么时候会在第i个号码.但这对我来说似乎不是最佳选择.

我可以在O(log n),我用来存储通用数字集的树的高度上执行此操作吗？

谢谢

Answer 1

如果你可以在节点中保留一些信息,你当然可以这样做.为了进行遍历O(logn),我们需要每个节点知道它的右子树有多少个节点.(您可以维护此信息,并且仍然在O(log(n))时间内添加/删除树)

def search(currentNode, k)
    if k == 0 then
        return currentNode
    else if currentNode.rightBranchSize >= k then
        // we remove 1 from k because currentNode isn't considered anymore
        return search(currentNode.right, k - 1)
    else
        // we decrease k because currentNode and its whole right subtree aren't considered anymore
        return search(currentNode.parent, k - currentNode.rightBranchSize - 1)
    end
end

代码应该是不言自明的.
我们从currentNode第一个带数字的节点开始>= A,寻找第k个元素(k是从0开始).

1. 作为他的评论中的schnaader,如果k很小的话就会更容易遍历树.
2. 大多数广泛传播的库(如STL)不允许以这种方式遍历树(它们不提供任何类型的Node结构,指向左右子树).因此,尽管算法很简单,但实现它可能很困难.
3. B从你的问题中只需要很少的修改.