CODEWITHSUNDEEP
c#.netalgorithmdata-structures
user7127000
user7127000

Reputation: 3233

Is it possible to build a binary tree and keep track of the median, still with O(log(n)) insertion?

I'm trying to figure out whether this is possible.

My attempt at an algorithm:

m1,m2 are the middle 2 elements (If the size of the tree is odd, then m1=m2).

Here's what building the tree might look like

----------------------------------
           5 = m1,m2
----------------------------------
           5 = m2
          /
         2 = m1
-----------------------------------
          5 
         /
        2 = m1,m2
       /
      1
-----------------------------------  
          5 
         /
        2 = m1
       / \ 
      1   3 = m2
-----------------------------------
          5
         / \
        2   9 
       / \ 
      1   3 = m1,m2
-----------------------------------
          5 = m2
         /  \
        2    9 
       / \   /
      1   \ 6   
           \
           3 = m1

and I started to try and implement the method

    /// <summary>
    /// Insert an element
    /// </summary>
    public void Insert(int val)
    {
        // If inserting first element, set _m1 and _m2.
        if(_root == null)
        {
            _m1 = _m2 = val;
        }

        // Insert new node in proper spot in tree.
        Node cur = _root;           
        while(cur != null)
        {
            if(cur.Val > val)
                cur = cur.Left;
            else if(cur.Val < val)
                cur = cur.Right;
            else // found value on an existing node
                return;
        }
        cur = new Node() { Val = val };

        // Update median elements
        if(val < _m1.Val)
        {
            // ???
        }
        else if(val > _m2.Val)
        {
            // ???
        }
    }       
}

but I can't figure out how to update the median. Is it even possible to do O(1) time?

Upvotes: 2

Views: 243

Answers (1)

HugoRune
HugoRune

Reputation: 13799

If you turn your tree into an order statistics tree (see also), you can look up the median in O(tree-height), so o(log(n)) if the tree is balanced.

To keep track of the median, you could simply perform a lookup of the median whenever you modify the tree.

To turn your tree into an order statistics tree, you need to store and update the nuber of descendants for each node inside the node, together with its value.

Someone posted a c#-Implementation of such a tree in this related answer.

Upvotes: 1

Related Questions