The Algorithm Design Manual (3rd) Exercise Solution 'E3-22'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-22

Question

Design a data structure that supports the following two operations:

• insert(x) – Insert item x from the data stream to the data structure.
• median() – Return the median of all elements so far.
  All operations must take $O(log n)$ time on an n-element set.

Solution

Conditions

We adopt binary search tree for this problem.
We consider tree node structure like this (C++ notation):

struct tree_node{
    int value;
    tree_node left;
    tree_node right;
    int num_of_left_children;
    int num_of_right_children;
}

num_of_left_children has the number of elements in left branch and so is num_of_right_children.

And we assume the tree's total size is always traced.

Routine

Median element is essentially $\left\lfloor\frac{n}{2}\right\rfloor$-th element of the ordered set.
So the routine for finding median element is specialized version of the routine for finding k-th element.

Finding-Kth-Element(k)
    Let t=root node
    Loop:
        If(k==0) then
            Return t.value
        Else If(k < t.num_of_left_children) then
            --k
            t=t.left
        Else
            k-=t.left+1
            t=t.right

The search only pass h nodes (h:tree's height), so it takes $O(logn)$ time.