BST median in O (logn) time complexity

Question

I met the solution indicated at http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8 using the Morris InOrder bypass, with which we can find the median in O(n) time.

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

Answer 1

If you also support counting the number of left and right descendants of a node, you can do this in O (logN) by searching for the median position. In fact, you can find the kth largest element in O (logn) time.

Of course, this suggests that the tree is balanced. Keeping the count does not change the complexity of the insert / delete.

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

See: Order a statistical tree .

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

Answer 2

If you do not guarantee some balanced tree, this is not possible.

Consider a tree that is completely degenerate - for example, each left pointer is NULL (nil, whatever), so each node has only the right child (that is, for all practical purposes, a "tree" is really a simply connected list).

In this case, just accessing the median node (generally) takes linear time - even if you started to know that node N is the median, it will still take N steps to get to this node.

Answer 3

We can find the median using the rabbit and turtle pointer. The rabbit moves twice as fast as the turtle, bypassing the ONT in order. Thus, when the rabbit reaches the end of the round, the turtle enters the BST median.

A detailed explanation is given .