Find median in O(1) in binary tree

Question

Suppose I have a balanced BST (binary search tree). Each tree node contains a special field count, which counts all descendants of that node + the node itself. They call this data structure order statistics binary tree.

This data structure supports two operations of O(logN):

• rank(x) -- number of elements that are less than x
• findByRank(k) -- find the node with rank == k

Now I would like to add a new operation median() to find the median. Can I assume this operation is O(1) if the tree is balanced?

Answer 1

Unless the tree is complete, the median might be a leaf node. So in general case the cost will be O(logN). I guess there is a data structure with requested properties and with a O(1) findMedian operation (Perhaps a skip list + a pointer to the median node; I'm not sure about findByRank and rank operations though) but a balanced BST is not one of them.