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) 最坏情况复杂度。

请参阅：订单统计树。

顺便说一句，BigO 和 Smallo 非常不同（你的标题是 Smallo）。

Answer 2

除非您保证某种平衡树，否则这是不可能的。

考虑一棵完全退化的树——例如，每个left指针都是NULL（nil，无论如何），所以每个节点只有一个右孩子（即，对于所有实际目的，“树”实际上是一个单链表）。

在这种情况下，仅仅访问中间节点（完全）需要线性时间——即使你一开始就知道节点 N 是中间节点，它仍然需要 N 步才能到达该节点。

Answer 3

我们可以使用rabbit和turtle指针找到中位数。在 BST 的有序遍历中，兔子的移动速度是乌龟的两倍。这样当兔子到达遍历结束时，乌龟就在 BST 的中间。

请查看完整说明。