471,585 Members | 1,607 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,585 software developers and data experts.

Help : Merging Binary Search Trees

Can someone help me with an algorithm to merge two binary search trees.

One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space. Can this be done more
efficiently ?
Please help me.

Dec 10 '05 #1
3 6393
In article <11**********************@g14g2000cwa.googlegroups .com>,
ptrSriram <sr********@gmail.com> wrote:
Can someone help me with an algorithm to merge two binary search trees. One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space. Can this be done more
efficiently ?


That depends. There are a number of different types of binary trees.
Is there some particular property imposed on the trees you are
using, such as that they must be "balanced" ? Do your tree entries
have back-pointers or just downward pointers?
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
Dec 10 '05 #2
Walter Roberson wrote:
ptrSriram <sr********@gmail.com> wrote:
Can someone help me with an algorithm to merge two binary
search trees.

One method I thought of was to flatten both the trees into
sorted lists(inorder traversal),merge those two sorted lists,
and build a binary search tree from the new list. But this
seems to be expensive in terms of space. Can this be done
more efficiently ?


That depends. There are a number of different types of binary
trees. Is there some particular property imposed on the trees
you are using, such as that they must be "balanced" ? Do your
tree entries have back-pointers or just downward pointers?


I think the question should be answered in terms of a minimal
organization. i.e. the fundamental data item should be very
similar to:

struct itemlink {
struct itemlink *left, *right;
void *dataptr;
};

together with some routine that will return a -1, 0, +1 comparison
result when passed two struct itemlink * pointers. Then the trees
to be merged are represented by two struct itemlink * pointers to
the roots of the two trees.

--
Read about the Sony stealthware that is a security leak, phones
home, and is generally illegal in most parts of the world. Also
the apparent connivance of the various security software firms.
http://www.schneier.com/blog/archive...drm_rootk.html
Dec 11 '05 #3
ptrSriram wrote:
Can someone help me with an algorithm to merge two binary search trees.

One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space.


Why would it be expensive in space? If the data is in a tree, each item
should be held in a node with two or more pointers. You should be able
to link the items into list, merge them, and place them in another tree
without any additional space.

--
Thad

Dec 12 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

12 posts views Thread by Vibhajha | last post: by
3 posts views Thread by tsunami | last post: by
8 posts views Thread by sudharsan | last post: by
10 posts views Thread by free2cric | last post: by
2 posts views Thread by pyguy | last post: by
4 posts views Thread by gagan.singh.arora | last post: by
6 posts views Thread by Henrik Goldman | last post: by
7 posts views Thread by Vinodh | last post: by
reply views Thread by XIAOLAOHU | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.