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.

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