Assume you have 2 AVL trees U and V and an element x such that every element in U is < x and every element in V is > x. How would you merge U, V, and x to create an AVL tree? What algorithm would create an O(log(n)) time complexity?
So I know the answer is that you simply create a BST with x as the root and U as left child and V as a right child, and then rebalance. But how do I justify that this has O(log(n)) complexity?
If both trees have the same height or differ by at most one, your approach is correct (and no balancing is needed). However, when they differ by more it is not.
We can solve the problem recursively:
def merge(U, x, V):
if h(V) > h(U) + 1:
V.left = merge(U, x, V.left)
# Note that h(V.left) can only increase, by at most 1,
# so one rotation can fix all issues.
if h(V.left) > h(V.right) + 1:
V = rotate-right(V)
return V
if h(U) > h(V) + 1:
U.right = merge(U.right, x, V)
if h(U.right) > h(U.left) + 1:
U = rotate-left(U)
return U
return new-node(x, U, V)
Note that we perform at most a constant amount of work in each call, plus an optional single recursive call. Therefore the complexity is O(recursion_depth). But it should also be easy to see that the recursion depth is limited by the difference in the height of the trees U, V. And each of those have heights that are O(log n), thus we can conclude merge is also O(log n).