O(logn) 时间复杂度中 BST 的中位数
我遇到了 http://discuss.joelonsoftware.com/default 给出的解决方案。 asp?interview.11.780597.8 使用 Morris InOrder 遍历，我们可以在 O(n) 时间内找到中位数。
但是是否可以使用 O(logn) 时间实现相同的目标？这里也提出了同样的问题 - http://www.careercup.com/question?id=192816
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.
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您还维护节点的左后代和右后代数量的计数，则可以通过搜索中值位置在 O(logN) 时间内完成。事实上，你可以在 O(logn) 时间内找到第 k 大元素。
当然，这是假设树是平衡的。维护计数不会改变插入/删除的复杂性。
如果树不平衡，则最坏情况复杂度为 Omega(n)。
请参阅：订单统计树。
顺便说一句，BigO 和 Smallo 非常不同（你的标题说 Smallo）。
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.
If the tree is not balanced, then you have Omega(n) worst case complexity.
See: Order Statistic Tree.
btw, BigO and Smallo are very different (your title says Smallo).
除非你保证某种平衡树，否则这是不可能的。
考虑一棵完全退化的树——例如，每个
left指针都是NULL（nil，无论如何），因此每个节点只有一个右子节点（即，出于所有实际目的，“树”实际上是一个单链表）。在这种情况下，仅仅访问中值节点（完全）就需要线性时间——即使您一开始就知道节点 N 是中值，仍然需要 N 个步骤才能到达该节点。
Unless you guarantee some sort of balanced tree, it's not possible.
Consider a tree that's completely degenerate -- e.g., every
leftpointer is NULL (nil, whatever), so each node only has a right child (i.e., for all practical purposes the "tree" is really a singly linked list).In this case, just accessing the median node (at all) takes linear time -- even if you started out knowing that node N was the median, it would still take N steps to get to that node.
我们可以使用
rabbit和turtle指针找到中位数。在 BST 的有序遍历中，兔子的移动速度是乌龟的两倍。这样，当兔子到达遍历终点时，乌龟就位于 BST 的中间位置。请参阅完整说明。
We can find the median by using the
rabbitand theturtlepointer. The rabbit moves twice as fast as the turtle in the in-order traversal of the BST. This way when the rabbit reaches the end of traversal, the turtle in at the median of the BST.Please see the full explanation.