Merging 2 DIFFERENT AVL trees

Question

Assume that I have two AVL trees and that I know their respective sizes. However, I don't know if there are repeated nodes, or any other information. What would be the most efficient way to merge them in a new AVL tree? The original trees can be destroyed.

Answer 1

1. Convert your trees T1 and T2 to sorted lists L1 and L2
2. Merge L1 and L2 into a sorted list L
3. Convert L into a tree T again.

IIRC all this operations are O(N), so the full merge will also be O(N).

If your representation of AVL trees allows to iterate over them efficiently (for instance, using backpointers, continuations, lazy evaluation, etc.) you should be able to do it also without the intermediate lists.

Update: as your programming language seems to be C/C++ you could temporarily abuse your AVL node estructures to be nodes in a linked list and later reuse them again for the output tree.

Update 2: @hwlau: this is O(N), I have checked it using my own AVL implementation in Prolog available from avl.pl and this test program avl_test.pl that checks the number of operations when merging AVL trees of size 1, 2, 4, 8, 16, ...

This is the output:

timing avl_merge, size: 128
% 1,790 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
timing avl_merge, size: 256
% 3,591 inferences, 0.010 CPU in 0.002 seconds (430% CPU, 359100 Lips)
timing avl_merge, size: 512
% 7,176 inferences, 0.030 CPU in 0.028 seconds (107% CPU, 239200 Lips)
...
timing avl_merge, size: 32000
% 451,839 inferences, 0.490 CPU in 0.499 seconds (98% CPU, 922120 Lips)
timing avl_merge, size: 64000
% 903,682 inferences, 0.900 CPU in 0.964 seconds (93% CPU, 1004091 Lips)
timing avl_merge, size: 128000
% 1,807,363 inferences, 2.420 CPU in 2.559 seconds (95% CPU, 746844 Lips)

Its obvious that the number of inferences/operations is proportional to the size of the merged trees and so the complexity of the algorithm O(N).

Answer 2

It is not the most efficient, but is definitely the easiest to implement. You can just add all nodes from second tree to the first. You don't need to remove the nodes from the second tree. You just destroy the second tree then and have the first tree as a result. The time complexity is O(N*log(N)).