Author |
Topic: Binary search tree merging (Read 11785 times) |
|
knuther
Newbie
Posts: 6
|
 |
Binary search tree merging
« on: Dec 9th, 2004, 1:04am » |
 Quote  Modify
|
Got this question recently in an interview.....
There are two unbalanced binary search trees say T1 and T2. Find an efficient algorithm to merge these two trees into a (Height) Balanced Binary search tree T3.
Brute force algorithm would require O(n logm)+Time for balancing with n being number of nodes in T1 and m being number of nodes in T2. or O(m log n) + Balancing time.
can we optimize on this using extra space?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #1 on: Dec 9th, 2004, 1:39am » |
Quote Modify
|
::How about flattening both trees into array's of length n and m respectively, then merging them together into an n+m array, and rebuild a tree from that.
Building a balanced tree from sorted data is easy enough after all.
Should be O(n+m)::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Binary search tree merging
« Reply #2 on: Dec 9th, 2004, 7:28am » |
Quote Modify
|
how do you do that (flattening)?
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #3 on: Dec 9th, 2004, 8:24am » |
Quote Modify
|
Put all the elements in the order that you encounter them in during a depth first traversal of the tree.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Binary search tree merging
« Reply #4 on: Dec 10th, 2004, 1:55pm » |
Quote Modify
|
I don't see how merging two flattened trees will optimize anything. Even with a mergesort on the arrays, that is O(log2n). Quicksort would be a crappy algorithm because the data is almost sorted. Combined with traversing a tree, O(n), and constructing a new one, O(nlog2n), there is no savings in time that I can see.
However, I seem to remember seeing another algorithm somewhere that might help. I will see if I can find it when I get home this afternoon.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #5 on: Dec 11th, 2004, 9:33am » |
Quote Modify
|
on Dec 10th, 2004, 1:55pm, John_Gaughan wrote:| I don't see how merging two flattened trees will optimize anything. Even with a mergesort on the arrays, that is O(log2n). |
|
They're allready sorted, so you only need to merge them.
traversing the trees and flattenign them is O(n) + O(m)=O(n+m)
Merging them is O(n+m)
Making a new balanced tree from the merged array is O(n+m)
So the total is O(n+m) which is better then O(n log m)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
knuther
Newbie
Posts: 6
|
|
Re: Binary search tree merging
« Reply #6 on: Dec 11th, 2004, 8:29pm » |
Quote Modify
|
TOWR is right.
The tree flattening will yeild sorted arrays if inorder traversal is done for the binary search tree ( left -root - right). This is O(n) and O(m)
Then we have to merge these two arrays which is O(n+m).
Now we have to build a balanced binary search tree from the sorted array. This can probably be done by starting at the middle element and assigning it as root and recursively applying the same function to the left subarray of the element
getting the left subtree's root and then to the right subarray of the element to get the right subtree's root.
The space overhead here is n+m(flattening)+n+m(merging...Inhouse merging is costly..)+n+m(building a balanced tree).
Can this be further optimized in terms of space consumed ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #7 on: Dec 12th, 2004, 12:12pm » |
Quote Modify
|
You don't have to explicitly flatten the trees before starting to merge them. You can do that while traversing both trees inorder.
And if you know how many elements there are, you can also start rebuilding the balanced tree without completing the merged array.. You would still need space to keep track of all the subtrees; I think that's in the order of the depth of the tree (at most one subtree for each level, because if you have two subtrees at one level they comprise a larger subtree at a higher level)
I probably wouldn't want to try that last optimalisation though, unless n+m was a power of two though..
|
| « Last Edit: Dec 12th, 2004, 12:19pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Binary search tree merging
« Reply #8 on: Dec 13th, 2004, 12:19pm » |
Quote Modify
|
Ah, I see now. Doing a preorder traversal will, of course, get all elements in ascending order: O(n+m). Merging into another array is trivial: O(n+m). Creating another tree using knuther's method is O(n+m). So the whole thing is O(n+m). But to do this you need to make the tree manually, getting old school. No STL or other prebaked solution here 
Actually, to address knuther's other issue, we don't have to create three arrays. Merge the trees into the array on the fly while traversing using the same method as merging two sorted arrays, treating the output of the preorder traversals as serialized arrays.
If we know the size of the original trees, we can forgo the intermediate array entirely by calculating the structure of the target tree and inserting nodes directly where they will wind up. This only works, however, if we have a priori knowledge of the tree's size.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Binary search tree merging
« Reply #10 on: Dec 13th, 2004, 1:02pm » |
Quote Modify
|
on Dec 13th, 2004, 12:33pm, towr wrote:yeah, that's what I said  |
|
Maybe I should have read your post first. The best place to hide something from me is out in the open 
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Binary search tree merging
« Reply #11 on: May 24th, 2007, 7:02am » |
Quote Modify
|
on Dec 12th, 2004, 12:12pm, towr wrote:| You don't have to explicitly flatten the trees before starting to merge them. You can do that while traversing both trees inorder. |
|
Ok . I Understood this one
on Dec 12th, 2004, 12:12pm, towr wrote:
And if you know how many elements there are, you can also start rebuilding the balanced tree without completing the merged array.. You would still need space to keep track of all the subtrees; I think that's in the order of the depth of the tree (at most one subtree for each level, because if you have two subtrees at one level they comprise a larger subtree at a higher level)
I probably wouldn't want to try that last optimalisation though, unless n+m was a power of two though.. |
|
But i didnt get this one . Can U please give some pseudocode/example
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #12 on: May 24th, 2007, 8:20am » |
Quote Modify
|
on May 24th, 2007, 7:02am, R0B1N wrote:But i didnt get this one . Can U please give some pseudocode/example
|
|
You use recursion, and treat the elements from the merging as an incoming stream.
Since you know the number of elements (which was given as an assumption), you know how many need to go to the first subtree and how many in the next subtree. And recursively you know it for each subtree.
So, I suppose
Code:
buildtree(stream &mergedstream, int size)
{
if (!size || !mergedstream)
return 0;
tree * node=new tree().
node->getValueFromStream(mergedstream);
if (size>1)
{
int leftsize= (size-1)/2;
int rightsize= size-1 - leftsize;
node->setLeft(buildtree(mergedstream, leftsize));
node->setRight(buildtree(mergedstream, rightsize));
}
}
|
|
|
| « Last Edit: May 24th, 2007, 8:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Binary search tree merging
« Reply #13 on: May 24th, 2007, 9:04am » |
Quote Modify
|
on May 24th, 2007, 8:20am, towr wrote:
You use recursion, and treat the elements from the merging as an incoming stream.
Since you know the number of elements (which was given as an assumption), you know how many need to go to the first subtree and how many in the next subtree. And recursively you know it for each subtree.
So, I suppose
Code:
buildtree(stream &mergedstream, int size)
{
if (!size || !mergedstream)
return 0;
tree * node=new tree().
node->getValueFromStream(mergedstream);
if (size>1)
{
int leftsize= (size-1)/2;
int rightsize= size-1 - leftsize;
node->setLeft(buildtree(mergedstream, leftsize));
node->setRight(buildtree(mergedstream, rightsize));
}
}
|
|
|
|
Ok , Just to make Sure i have understood it correctly ....
Here
Code:
....
....
tree * node=new tree().
node->getValueFromStream(mergedstream);
....
.... |
|
getValueFromStream() is Nothing But the The Merged Input Treated as Preoder Traversal of the Merged Tree , Right ? .
Hmmmm Thats what above 2 posts says , Hmmm Now i have understood it correctly
Thanks Towr
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #14 on: May 24th, 2007, 12:53pm » |
Quote Modify
|
on May 24th, 2007, 9:04am, R0B1N wrote:Ok , Just to make Sure i have understood it correctly ....
Here
Code:
....
....
tree * node=new tree().
node->getValueFromStream(mergedstream);
....
.... |
|
getValueFromStream() is Nothing But the The Merged Input Treated as Preoder Traversal of the Merged Tree , Right ? |
|
getValueFromStream() takes the next piece of data from "mergedstream" and puts it in the node. The "mergedstream" can be seen as the inorder traversal of the merged tree (or more accurately, it's the merger of the two inorder traversals of the input trees).
From this you can surmise that I have in fact made a mistake in my pseudocode.
It should be:
Code:buildtree(stream &mergedstream, int size)
{
if (!size || !mergedstream)
return 0;
tree * node=new tree().
if (size=1)
node->getValueFromStream(mergedstream);
else
{
int leftsize= (size-1)/2;
int rightsize= size-1 - leftsize;
node->setLeft(buildtree(mergedstream, leftsize));
node->getValueFromStream(mergedstream);
node->setRight(buildtree(mergedstream, rightsize));
}
} |
|
|
| « Last Edit: May 24th, 2007, 12:54pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
arunrambo2000
Newbie
Posts: 21
|
|
Re: Binary search tree merging
« Reply #15 on: May 28th, 2007, 12:09pm » |
Quote Modify
|
I think for merging using an extra array may be costly... so i think we can go inorder traversal simultaneously and put the elements in sorted order in an array of O(m+n) in O(m+n)..
Then we can rebuild the new BST from the array as Knuther specified in a recursive manner in O(m+n)
|
| « Last Edit: May 28th, 2007, 12:14pm by arunrambo2000 » |
IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Binary search tree merging
« Reply #16 on: May 29th, 2007, 12:12am » |
Quote Modify
|
on May 28th, 2007, 12:09pm, arunrambo2000 wrote:I think for merging using an extra array may be costly... so i think we can go inorder traversal simultaneously and put the elements in sorted order in an array of O(m+n) in O(m+n)..
|
|
Thats what the discussion is about and in the above method we not even using extra O(m+n) space for merged array
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: Binary search tree merging
« Reply #17 on: Jul 19th, 2007, 12:14am » |
Quote Modify
|
Towr ..
Don't you think your "on the fly" build of the "merged" bst, when the number of elements is known a priori, takes O(n lgn) time in the worst case, as we are inserying each element, each of which may take time O(lg n) time ..
NOTE :: Here n = total number of nodes from the two original treees
|
|
IP Logged |
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: Binary search tree merging
« Reply #18 on: Jul 19th, 2007, 12:35am » |
Quote Modify
|
Moreover, I also find it hard to think that getting a sorted merged entity of two trees (without using O(n) and O(m) array space) can be done PRACTICALLY. Assuming that the nodes do not contain a parent pointer, we will have to implement this strategy using iterative versions, using explicit stacks. That might itself lend to using O(n+m) space, (albeit it will be called extra stack space, not extra array space  )
What do you think ..?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #19 on: Jul 19th, 2007, 1:18am » |
Quote Modify
|
on Jul 19th, 2007, 12:14am, u_think_u_succeed wrote:Towr ..
Don't you think your "on the fly" build of the "merged" bst, when the number of elements is known a priori, takes O(n lgn) time in the worst case, as we are inserting each element, each of which may take time O(lg n) time .. |
|
No, the input is already sorted, so each element can be put in place in O(1) time.
The same as if you were merging two sorted array into a sorted array. Making a sorted array from two unsorted ones would take O(n log n), but given they're sorted it's O(n).
And this problem is equivalent to that. (It's easy to turn a bst into an array in O(n), and vice versa in the same time)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #20 on: Jul 19th, 2007, 1:28am » |
Quote Modify
|
on Jul 19th, 2007, 12:35am, u_think_u_succeed wrote:| Moreover, I also find it hard to think that getting a sorted merged entity of two trees (without using O(n) and O(m) array space) can be done PRACTICALLY. |
|
There is an algorithm given; although some elements of it need to be implemented. It's certainly easier to use intermediate arrays, but it by no means necessary.
Quote:| Assuming that the nodes do not contain a parent pointer, we will have to implement this strategy using iterative versions, using explicit stacks. |
|
Using the function stack might suffice. And you can manipulate the content of the tree in such a way that you only need a constant number of extra pointers (but that's hell in a handbasket).
Quote:| That might itself lend to using O(n+m) space, (albeit it will be called extra stack space, not extra array space ) |
|
The maximum number of parents a node in a (reasonably balanced) tree would have is log(n), so the total extra space would be O(log(n)+log(m)).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Binary search tree merging
« Reply #21 on: Mar 9th, 2008, 10:32pm » |
Quote Modify
|
on Jul 19th, 2007, 1:18am, towr wrote:
No, the input is already sorted, so each element can be put in place in O(1) time.
The same as if you were merging two sorted array into a sorted array. Making a sorted array from two unsorted ones would take O(n log n), but given they're sorted it's O(n).
And this problem is equivalent to that. (It's easy to turn a bst into an array in O(n), and vice versa in the same time) |
|
Could you please tell how to build a bst from a sorted array in O(n)? Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary search tree merging
« Reply #22 on: Mar 10th, 2008, 2:05am » |
Quote Modify
|
on Mar 9th, 2008, 10:32pm, mad wrote:| Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on? |
|
Yes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Binary search tree merging
« Reply #23 on: Mar 10th, 2008, 2:24am » |
Quote Modify
|
on Dec 9th, 2004, 1:04am, knuther wrote:Got this question recently in an interview.....
There are two unbalanced binary search trees say T1 and T2. Find an efficient algorithm to merge these two trees into a (Height) Balanced Binary search tree T3.
Brute force algorithm would require O(n logm)+Time for balancing with n being number of nodes in T1 and m being number of nodes in T2. or O(m log n) + Balancing time.
can we optimize on this using extra space? |
|
a) Convert both the bst into sorted doubly linked lists in O(n+m) time.
b)merge the two double linked lists into one and also maintain the count of total elements in O(n+m) time.
c)convert the sorted doubly linked list into height balacned tree in O(n+m) time.
It takes O(n+m) time and O(1) space.
|
| « Last Edit: Mar 10th, 2008, 2:26am by m_aakash » |
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Binary search tree merging
« Reply #24 on: Mar 10th, 2008, 2:30am » |
Quote Modify
|
on Mar 9th, 2008, 10:32pm, mad wrote:
Could you please tell how to build a bst from a sorted array in O(n)? Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on?
|
|
Taking middle and building left and right subtrees is one approach.
Other way is that since u know the number of elements in the array, build the tree recursively with the count and while coming from bottom of the recursion u can fill the tree node values with given array elements in sequence as well.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print