Thread: Get median from avl tree?

If you have an avl tree, whats the best way to get the median from it? The median would be defined as the element with index ceil(n/2) (index starts with 1) in the sorted list.
So if the list was 1 3 5 7 8
median is 5
if the list was 1 3 5 7 8 10
median is 5
Assume you can augment the tree. In this case, I think it's best to let each node know the size (number of nodes) of the subtree, (i.e. 1+left.size+right.size)
But using this, the best way I can think of makes median searching O(lg n) time because you can traverse by comparing indexes. Is there a better way?

Hey Sneaky.

One suggestion for you if you need to speed up time is to create another data structure with median info that is synched to the tree and gets updated every time the contents of the tree change.

That way you trade some memory for speed.

Can you explain how this would work? What if a node gets deleted or added, how do you manage the median value?

You just update the new structure every time an add or a delete happens.

You could keep a separate structure for an ordered list of node numbers (i.e. sorted in ascending order) and the add/delete methods just update this structure on an add or delete.

For an avl tree, is it possible to alter the algorithms (assuming each node knows the size of it's sub tree which is node.size = 1 + node.left.size + node.right.size) so that when ever you delete or insert, the median always stays at the root of the whole data structure?

Here is an idea.

Have an array or linked list that contains a set of structures: each structure has a pointer to a particular node and also has a number corresponding to number of nodes.

Now every-time you delete a node, you synch with this list. Every time you add a node, you also synch to the list.

The list is sorted according to node count. Now every time the tree is modified, you re-calculate the median.

Another way to solve this is to make a binary tree with the nodes being the node count of each tree. You then traverse the tree in the optimal way to get the median value.

There are other possibilities for doing fast median calculation and lookup.