Get median from AVL tree?

Question

If you have an AVL tree, what's the best way to get a median from it? The median will be defined as the element with index ceil (n / 2) (index starts at 1) in the sorted list.

So, if the list was

1 3 5 7 8 

the median is 5. If the list was

1 3 5 7 8 10

the median is 5.

If you can enlarge the tree, I think it is best to tell each node the size (number of nodes) of the subtree (i.e. 1 + left.size + right.size). Using this, the best way I can think of is doing a median search of O (log n), because you can navigate by comparing indices.

Is there a better way?

Answer 1

Extending the AVL tree to store subtree sizes is usually the best approach here if you need to optimize median queries. It takes O (log n) time, which is pretty fast.

If you will calculate the median a huge number of times, you can use the extended tree and also cache the median value so that you can read it in time O (1). Each time you insert or delete, you may need to recalculate the median in time O (log n), which will slow down the work a little, but will not affect the asymptotic costs.

Another option would be to swap the doubly linked list through nodes in the tree so that you can navigate from node to your successor or predecessor in constant time. If you do, you can save a pointer to the median element, and then insert or delete, move the pointer left or right, if necessary. If you delete the median information, you can simply move the pointer left or right as you would like. This does not require any increase and may be slightly faster, but adds two additional pointers to each node.

Hope this helps!