Search code examples
median

Finding continuous median

How would you compute the medians for a given input that updates every time a new input is added? For example:

  • 1 - Median is 1
  • 1,2 - Median is 3/2
  • 1,2,3 - Median is 2
Solution

  • You can do it in O(logn) per element.

    Build AVL tree (or RBT), set one pointer to median. And now augment AVL with full threads (both), parent pointer.
    Insert time is logarithmic, successor and predecessor is constant operation, thus updating median pointer is constant time operation.

    Parent pointer plus threads might seem redundant, but this guarantees no traversal, median update is done in rotation phase.

    Pros: only insertion time matters. Structure is dynamic, no need to reallocate array or move elements.

    Cons: there is overhead in space and allocating nodes.