Concatenating/Merging/Joining two AVL trees

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)