Given that integers are read from a data stream. Find median of elements read so for in efficient way

Question

Can we use AVL tree for this, so that root element is the median at any point

If you read them from a stream will this increase performance? — Adriano Repetti, Feb 28 '13 at 12:36
See http://stackoverflow.com/questions/1387497/find-median-value-from-a-growing-set — Vincent van der Weele, Feb 28 '13 at 12:40

score 1 · Accepted Answer · answered Feb 28 '13 at 12:37

1

No, AVL-trees are height-balanced, you need a weight-balanced tree.

answered Feb 28 '13 at 12:37

kutschkem

u can have mixture of BST and AVL step 1-insert a number based on value (right or left) step 2-balance tree – rohitmb Feb 28 '13 at 12:48
well but what you actually mean is balancing based on the number of nodes in the subtrees. The AVL-criterion is balancing based on the height of the subtrees, which is not what you want for getting the median value. – kutschkem Feb 28 '13 at 13:54

1 Answers1