wu :: forums - Print Page


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

        riddles >> cs >> Binary search tree merging
        
(Message started by: knuther on Dec 9^th, 2004, 1:04am)

Title: Binary search tree merging
Post by knuther on Dec 9^th, 2004, 1:04am

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?

Title: Re: Binary search tree merging
Post by towr on Dec 9^th, 2004, 1:39am

::[hide]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)[/hide]::

Title: Re: Binary search tree merging
Post by puzzlecracker on Dec 9^th, 2004, 7:28am

how do you do that (flattening)?

Title: Re: Binary search tree merging
Post by towr on Dec 9^th, 2004, 8:24am

Put all the elements in the order that you encounter them in during a depth first traversal of the tree.

Title: Re: Binary search tree merging
Post by John_Gaughan on Dec 10^th, 2004, 1:55pm

I don't see how merging two flattened trees will optimize anything. Even with a mergesort on the arrays, that is O(log₂n). 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(nlog₂n), 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.

Title: Re: Binary search tree merging
Post by towr on Dec 11^th, 2004, 9:33am

on 12/10/04 at 13:55:27, 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(log₂n).

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)

Title: Re: Binary search tree merging
Post by knuther on Dec 11^th, 2004, 8:29pm

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 ?

Title: Re: Binary search tree merging
Post by towr on Dec 12^th, 2004, 12:12pm

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..

Title: Re: Binary search tree merging
Post by John_Gaughan on Dec 13^th, 2004, 12:19pm

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.

Title: Re: Binary search tree merging
Post by towr on Dec 13^th, 2004, 12:33pm

yeah, that's what I said ::)

Title: Re: Binary search tree merging
Post by John_Gaughan on Dec 13^th, 2004, 1:02pm

on 12/13/04 at 12:33:52, 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 ;D

Title: Re: Binary search tree merging
Post by R0B1N on May 24^th, 2007, 7:02am

on 12/12/04 at 12:12:47, 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 12/12/04 at 12:12:47, 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
???

Title: Re: Binary search tree merging
Post by towr on May 24^th, 2007, 8:20am

on 05/24/07 at 07:02:01, 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));
}
}

Title: Re: Binary search tree merging
Post by R0B1N on May 24^th, 2007, 9:04am

on 05/24/07 at 08:20:22, towr 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 ? .

Hmmmm Thats what above 2 posts says , Hmmm Now i have understood it correctly ;D

Thanks Towr

Title: Re: Binary search tree merging
Post by towr on May 24^th, 2007, 12:53pm

on 05/24/07 at 09:04:54, 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));
}
}

Title: Re: Binary search tree merging
Post by arunrambo2000 on May 28^th, 2007, 12:09pm

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)

Title: Re: Binary search tree merging
Post by R0B1N on May 29^th, 2007, 12:12am

on 05/28/07 at 12:09:54, 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
::)

Title: Re: Binary search tree merging
Post by u_think_u_succeed on Jul 19^th, 2007, 12:14am

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

Title: Re: Binary search tree merging
Post by u_think_u_succeed on Jul 19^th, 2007, 12:35am

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 :o )

What do you think ..?

Title: Re: Binary search tree merging
Post by towr on Jul 19^th, 2007, 1:18am

on 07/19/07 at 00:14:21, 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)

Title: Re: Binary search tree merging
Post by towr on Jul 19^th, 2007, 1:28am

on 07/19/07 at 00:35:08, 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 :o )

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)).

Title: Re: Binary search tree merging
Post by mad on Mar 9^th, 2008, 10:32pm

on 07/19/07 at 01:18:10, towr 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?

Title: Re: Binary search tree merging
Post by towr on Mar 10^th, 2008, 2:05am

on 03/09/08 at 22:32:07, 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.

Title: Re: Binary search tree merging
Post by m_aakash on Mar 10^th, 2008, 2:24am

on 12/09/04 at 01:04:14, knuther wrote:

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.

Title: Re: Binary search tree merging
Post by m_aakash on Mar 10^th, 2008, 2:30am

on 03/09/08 at 22:32:07, 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.