wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Merging a forest
        
(Message started by: first on Mar 8^th, 2008, 3:27am)

Title: Merging a forest
Post by first on Mar 8^th, 2008, 3:27am

A given tree can be broken into a forest by splitting the tree at various nodes. Here splitting means that the node at which you split become a leaf node of the original tree and also the root of the next tree.
So given such a forrest: Given an algorithm to efficiently merge such a forest back into a tree in O(n).

Title: Re: Merging a forest
Post by mad on Mar 8^th, 2008, 3:29am

Think this is similar to
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102583054;start=20#20

Title: Re: Merging a forest
Post by towr on Mar 8^th, 2008, 6:02am

[hide]You can use a hashmap to unify nodes in O(n)[/hide]

Title: Re: Merging a forest
Post by mad on Mar 9^th, 2008, 10:33pm

Could you explain what you mean?

Title: Re: Merging a forest
Post by towr on Mar 10^th, 2008, 2:07am

on 03/09/08 at 22:33:37, mad wrote:

Could you explain what you mean?

Put all leaf nodes in the hashmap, then for each root node, if it matches a leaf node, add the left and right subtree of the root node to the leaf and clear the entry from the hashmap.