algorithm - O(logn) 时间复杂度中 BST 的中值

Question

我遇到了 http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8 给出的解决方案使用 Morris InOrder 遍历，我们可以在 O(n) 时间内找到中位数。

但是否有可能使用 O(logn) 时间实现相同的效果？同样的问题在这里被问到 - http://www.careercup.com/question?id=192816

Answer 1

如果您还维护节点左右后代的数量，则可以在 O(logN) 时间内完成，方法是搜索中间位置。事实上，您可以在 O(logn) 时间内找到第 k 个最大的元素。

当然，这是假设树是平衡的。保持计数不会改变插入/删除的复杂性。

如果树不平衡，那么您的最坏情况复杂度为 Omega(n)。

参见:Order Statistic Tree .

顺便说一句，BigO 和 Smallo 非常不同(您的标题说 Smallo)。