wu :: forums « wu :: forums - Merging a forest » Welcome, Guest. Please Login or Register. Dec 21st, 2024, 9:23pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Grimbal, william wu, ThudnBlunder, Icarus, Eigenray, towr, SMQ)    Merging a forest « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Merging a forest  (Read 1294 times) first Newbie     Posts: 22 Merging a forest   « on: Mar 8th, 2008, 3:27am » Quote Modify 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). IP Logged mad Junior Member     Posts: 118 Re: Merging a forest   « Reply #1 on: Mar 8th, 2008, 3:29am » Quote Modify 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 IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Merging a forest   « Reply #2 on: Mar 8th, 2008, 6:02am » Quote Modify You can use a hashmap to unify nodes in O(n) IP Logged Wikipedia, Google, Mathworld, Integer sequence DB mad Junior Member     Posts: 118 Re: Merging a forest   « Reply #3 on: Mar 9th, 2008, 10:33pm » Quote Modify Could you explain what you mean? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Merging a forest   « Reply #4 on: Mar 10th, 2008, 2:07am » Quote Modify on Mar 9th, 2008, 10:33pm, 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. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board