BST中位数O（logn）时间复杂度 [英] Median of BST in O(logn) time complexity

问题描述

我发现在 http://discuss.joelonsoftware.com上提供的解决方案/default.asp?interview.11.780597.8 使用Morris InOrder遍历，我们可以在 O（n）时间中找到中位数。

I came across solution given at http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8 using Morris InOrder traversal using which we can find the median in O(n) time.

但是可以使用 O（logn）实现相同的时间吗？这里也提到了这一点 - http://www.careercup.com/question?id=192816

But is it possible to achieve the same using O(logn) time? The same has been asked here - http://www.careercup.com/question?id=192816

推荐答案

如果您还保留一个节点的左后卫人数，可以做它在O（logN）时间，通过搜索中位数。实际上，您可以在O（logn）时间中找到第k个最大元素。

If you also maintain the count of the number of left and right descendants of a node, you can do it in O(logN) time, by doing a search for the median position. In fact, you can find the kth largest element in O(logn) time.

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

Of course, this assumes that the tree is balanced. Maintaining the count does not change the insert/delete complexity.

如果树不平衡，那么您有Omega（n）最坏的情况复杂度。

If the tree is not balanced, then you have Omega(n) worst case complexity.

请参阅：订单统计树。

btw，BigO和Smallo是非常不同的（你的头衔说Smallo）。

btw, BigO and Smallo are very different (your title says Smallo).

这篇关于BST中位数O（logn）时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！