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:
left
tree (rotating and adjusting its computed height if necessary). Let n
be that element. O(log n)left
. Let r
be that node. O(log n)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
.
increment its parent's balance accordingly. O(1)