Merging two AVL treees

[gagan.singh.arora]

I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations. Some had done it by using an array, sorted the elements
and then formed the tree. Is there any sort of 'appropriate' algorithm
for doing this? (This seems sort of brute force).

 

[Richard Bos]

I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations.

Cannot be done, for exceedingly obvious reasons.

Some had done it by using an array, sorted the elements
and then formed the tree.

And how, then, did he "form the tree" without using any AVL tree
operations? It seems to me that building an AVL tree _is_ an AVL tree
operation.

Is there any sort of 'appropriate' algorithm for doing this?

Yes. Use the tools. Don't work around them.

Richard

 

[user923005]

I had a test today and there was a question regarding how to merge two
AVL trees to form another AVL tree without using any AVL tree
operations. Some had done it by using an array, sorted the elements
and then formed the tree. Is there any sort of 'appropriate' algorithm
for doing this? (This seems sort of brute force).

You want where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).

I guess that merging two properly formed AVL trees can be a lot more
efficient than simply cramming the smaller tree into the larger, one
object at a time, if there is a merge() function.

But your question is not a C question but an algorithm question.
While is not exactly an algorithms group, it's
the closest thing that I know of.

 

[Gene]

You want where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).

I guess that merging two properly formed AVL trees can be a lot more
efficient than simply cramming the smaller tree into the larger, one
object at a time, if there is a merge() function.

But your question is not a C question but an algorithm question.
While is not exactly an algorithms group, it's
the closest thing that I know of.

This article

http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e?

discusses how to build a balanced BST in O(n) time with O(log n) space
if you have input that's already sorted. So to merge _any_ set of
binary BSTs, just traverse them with in-order iterators, always
picking the least iterator value, and inserting this value into a new
balanced BST. It's easy to set the AVL flags on the fly as the new BST
is created or afterward in a separate O(n) pass.

 

[Ben Pfaff]

You want where you will (no doubt) run into Ben
Pfaff (who is quite the AVL tree expert).

I think that this question is answered in Knuth. It's actually
a coding exercise that I've never properly explored. Perhaps I
will do so for the next version of libavl, should I ever acquire
a round tuit.