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)

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.

I suspect that you'll just have to walk one tree (hopefully the smaller) and individually add each of it's elements to the other tree. The AVL insert/delete operations are not designed to handle adding a whole subtree at a time.