Help : Merging Binary Search Trees

Discussion in 'C Programming' started by ptrSriram, Dec 10, 2005.

1. ptrSriramGuest

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 ?

ptrSriram, Dec 10, 2005

2. Walter RobersonGuest

In article <>,
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. 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

Walter Roberson, Dec 10, 2005

3. Chuck F.Guest

Walter Roberson wrote:
> 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. 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/archives/2005/11/sonys_drm_rootk.html

Chuck F., Dec 10, 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