Geek asks and answers

Find the median in O (1) in a binary tree

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

This data structure supports two O (logN) operations:

  • rank(x) - number of elements smaller x
  • findByRank(k)- find node using rank==k

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

+5
source share
3 answers

If the tree is complete (i.e. all levels are completely filled), yes, you can.

+1

, node. O (logN). , O (1) findMedian (, + node; , findByRank ), BST .

+2

, , O (log N). O (1) , , . , , , . O (log N), O (log N), O.

, , " " /.

If you wish, you can reduce the cost of updating the median pointer during input / deletion to O (1) by using (twice) a threaded binary tree , but Insert / Delete will still be O (log N).

+1
source

More articles:


All Articles