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)最坏情况的复杂性.

请参阅:订单统计树.

顺便说一下,BigO和Smallo非常不同(你的标题是Smallo).