Results 1 to 6 of 6

Math Help - Get median from avl tree?

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Get median from avl tree?

    If you have an avl tree, whats the best way to get the median from it? The median would be defined as the element with index ceil(n/2) (index starts with 1) in the sorted list.
    So if the list was 1 3 5 7 8
    median is 5
    if the list was 1 3 5 7 8 10
    median is 5
    Assume you can augment the tree. In this case, I think it's best to let each node know the size (number of nodes) of the subtree, (i.e. 1+left.size+right.size)
    But using this, the best way I can think of makes median searching O(lg n) time because you can traverse by comparing indexes. Is there a better way?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,668
    Thanks
    608

    Re: Get median from avl tree?

    Hey Sneaky.

    One suggestion for you if you need to speed up time is to create another data structure with median info that is synched to the tree and gets updated every time the contents of the tree change.

    That way you trade some memory for speed.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Get median from avl tree?

    Can you explain how this would work? What if a node gets deleted or added, how do you manage the median value?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,668
    Thanks
    608

    Re: Get median from avl tree?

    You just update the new structure every time an add or a delete happens.

    You could keep a separate structure for an ordered list of node numbers (i.e. sorted in ascending order) and the add/delete methods just update this structure on an add or delete.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Get median from avl tree?

    For an avl tree, is it possible to alter the algorithms (assuming each node knows the size of it's sub tree which is node.size = 1 + node.left.size + node.right.size) so that when ever you delete or insert, the median always stays at the root of the whole data structure?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,668
    Thanks
    608

    Re: Get median from avl tree?

    Here is an idea.

    Have an array or linked list that contains a set of structures: each structure has a pointer to a particular node and also has a number corresponding to number of nodes.

    Now every-time you delete a node, you synch with this list. Every time you add a node, you also synch to the list.

    The list is sorted according to node count. Now every time the tree is modified, you re-calculate the median.

    Another way to solve this is to make a binary tree with the nodes being the node count of each tree. You then traverse the tree in the optimal way to get the median value.

    There are other possibilities for doing fast median calculation and lookup.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mean and median.
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 29th 2011, 09:07 PM
  2. Median help
    Posted in the Statistics Forum
    Replies: 6
    Last Post: January 10th 2011, 11:54 AM
  3. Mean and median.
    Posted in the Statistics Forum
    Replies: 2
    Last Post: August 23rd 2010, 05:04 PM
  4. Median
    Posted in the Statistics Forum
    Replies: 4
    Last Post: July 5th 2010, 07:21 PM
  5. Median
    Posted in the Statistics Forum
    Replies: 2
    Last Post: July 3rd 2007, 11:58 AM

Search Tags


/mathhelpforum @mathhelpforum