Concatenating/Merging/Joining two AVL trees

Question

Assume that I have two AVL trees and that each element from the first tree is smaller then any element from the second tree. What is the most efficient way to concatenate them into one single AVL tree? I've searched everywhere but haven't found anything useful.

Solution 1

Assuming you may destroy the input trees:

1. remove the rightmost element for the left tree, and use it to construct a new root node, whose left child is the left tree, and whose right child is the right tree: O(log n)
2. determine and set that node's balance factor: O(log n). In (temporary) violation of the invariant, the balance factor may be outside the range {-1, 0, 1}
3. rotate to get the balance factor back into range: O(log n) rotations: O(log n)

Thus, the entire operation can be performed in O(log n).

Edit: On second thought, it is easier to reason about the rotations in the following algorithm. It is also quite likely faster:

1. Determine the height of both trees: O(log n).
   Assuming that the right tree is taller (the other case is symmetric):
2. remove the rightmost element from the left tree (rotating and adjusting its computed height if necessary). Let n be that element. O(log n)
3. In the right tree, navigate left until you reach a node whose subtree is at most one 1 taller than left. Let r be that node. O(log n)

4. replace that node with a new node with value n, and subtrees left and r. O(1)
   By construction, the new node is AVL-balanced, and its subtree 1 taller than r.

5. increment its parent's balance accordingly. O(1)

6. and rebalance like you would after inserting. O(log n)

Solution 2

One ultra simple solution (that works without any assumptions in the relations between the trees) is this:

1. Do a merge sort of both trees into one merged array (concurrently iterate both trees).
2. Build an AVL tree from the array - take the middle element to be the root, and apply recursively to left and right halves.

Both steps are O(n). The major issue with it is that it takes O(n) extra space.

Solution 3

The best solution I read to this problem can be found here. Is very close to meriton's answer if you correct this issue:

In the third step of the algorithm navigates left until you reach the node whose sub tree has the same height as the left tree. This is not always possible, (see counterexample image). The right way to do this step is two find for a subtree with height h or h+1 where h is the height of the left tree