Velocity Reviews > Help : Merging Binary Search Trees

# Help : Merging Binary Search Trees

ptrSriram
Guest
Posts: n/a

 12-10-2005
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 ?

Walter Roberson
Guest
Posts: n/a

 12-10-2005
In article <(E-Mail Removed) .com>,
ptrSriram <(E-Mail Removed)> 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

Chuck F.
Guest
Posts: n/a

 12-10-2005
Walter Roberson wrote:
> ptrSriram <(E-Mail Removed)> 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:

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.

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

Guest
Posts: n/a

 12-12-2005
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

--