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.
Assuming you may destroy the input trees:
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:
lefttree (rotating and adjusting its computed height if necessary). Let
nbe that element. O(log n)
rbe that node. O(log n)
replace that node with a new node with value n, and subtrees
By construction, the new node is AVL-balanced, and its subtree 1 taller than
increment its parent's balance accordingly. O(1)
One ultra simple solution (that works without any assumptions in the relations between the trees) is this:
Both steps are O(n). The major issue with it is that it takes O(n) extra space.