BST在O（LOGN）的时间复杂度平均 [英] Median of BST in O(logn) time complexity

问题描述

我碰到的 http://discuss.joelonsoftware.com/给出的解决方案Default.asp的？interview.11.780597.8 使用使用它我们可以发现，在中位数莫里斯序遍历 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.

如果树是不均衡的，那么你有欧米茄（n）的最坏情况下的复杂性。

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

请参阅：次序统计树。

顺便说一句，比戈和Smallo有很大的不同（你的标题说Smallo）。

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

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