[algogeeks] Efficient Algo for Merging 2 Binary Search Trees
Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Efficient Algo for Merging 2 Binary Search Trees
Inorder traversal of one tree insert into another? On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg ankurga...@gmail.com wrote: Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Efficient Algo for Merging 2 Binary Search Trees
Actually, it doesn't have to be inorder. The naive approach is to traverse through the smaller tree (using any traversal in|pre|post|level order) and insert each node into the bigger tree. The order of this would be n2logn1 A better approach is to try and fit as much of the smaller bst into the larger bst. To explain, imagine the second (and smaller) bst can go and fit snugly as a leaf of the first bst, then you just need to do a logn1 traversal to find this location to insert the smaller bst into the larger bst. However you might not always have a spot in the first bst for the second bst to go as a whole. Here you break up the second tree into three pieces, root node, left subtree and right subtree. You insert the root node into BST1 and recursively call the merge on BST1 LeftSubTreeOfBST2 AND BST1 and RightSubTreeOfBST2. I think the worst case of this is not going to be much better than the naive approach but asymptotically this one should kick ass. ( To ensure that an adversary cannot make it perform badly, we can decide which BST to use as bst1 randomly.) Can anyone try and deduce the actual order of this algorithm (if it works) merge (bst1, bst2): if (bst2 is null) return bst1 if (bst1 is null) return bst2 if (bst2.max_element bst1.val) bst1.left = merge (bst1.left, bst2) else if (bst2.min_element bst1.val) bst1.right = merge (bst1.right, bst2) else // it means bst2 needs to be split up right away insertIntoBst(bst1, bst2.val) bst1 = merge (bst1, bst2.left) bst1 = merge (bst1, bst2.right) On Sun, Oct 9, 2011 at 3:38 AM, Vandana Bachani vandana@gmail.comwrote: Inorder traversal of one tree insert into another? On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg ankurga...@gmail.com wrote: Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Efficient Algo for Merging 2 Binary Search Trees
Recursively store parent and child pointers of the to-be-inserted tree using post-order traversal,and when processing each node during traversal reassign pointers to the other tree using BST insertion. Inorder may not work due to distortion of parent pointers? On Sun, Oct 9, 2011 at 3:38 AM, Vandana Bachani vandana@gmail.comwrote: Inorder traversal of one tree insert into another? On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg ankurga...@gmail.com wrote: Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
