Find Median from Running Data Stream using Augmented self-balanced binary search tree (AVL, RB, etc…)

• At every node of BST, maintain a number of elements in the subtree rooted at that node. We can use a node as the root of a simple binary tree, whose left child is self-balancing BST with elements less than root and right child is self-balancing BST with elements greater than root. The root element always holds effective median.
• If the left and right subtrees contain a same number of elements, the root node holds the average of left and right subtree root data. Otherwise, the root contains the same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed atmost by 1.
• Self-balancing BST is costly in managing the balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method makes use of Heaps to trace the median.

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

There are two cases for median on the basis of data set size.

• If the data set has an odd number then the middle one will be consider as median.
• If the data set has an even number then there is no distinct middle value and the median will be the arithmetic mean of the two middle values.

Example:

Input Data Stream: 5, 15, 1, 3
Output: 5, 10,5, 4
Explanation:
After reading 1st element of stream – 5 -> median = 5
After reading 2nd element of stream – 5, 15 -> median = (5+15)/2 = 10
After reading 3rd element of stream – 5, 15, 1 -> median = 5
After reading 4th element of stream – 5, 15, 1, 3 -> median = (3+5)/2 = 4

Input Data Stream: 2, 2, 2, 2
Output: 2, 2, 2, 2
Explanation:
After reading 1st element of stream – 2 -> median = 2
After reading 2nd element of stream – 2, 2 -> median = (2+2)/2 = 2
After reading 3rd element of stream – 2, 2, 2 -> median = 2
After reading 4th element of stream – 2, 2, 2, 2 -> median = (2+2)/2 = 2