Merging n AVL trees

Question

I have n AVL trees of sizes n_1,n_2,...,n_n so that sum(n_i)=n . I can merge two AVLs in linear time of the size of the bigger one. In how much time can I merge these n trees? Thx for any help

Answer 1

If you have k different trees, then you need to do a total of (k - 1) merges to collect them together into a single tree. So the question is how long each merge is going to take.

Suppose that you adopt the strategy that you always merge the two smallest trees together at any point in time. If you have m trees available when you do this, then the second-smallest tree's size will dominate the runtime of the merge. This size is at most (n - 1) / (k - 1), which happens when the smallest tree has just one element and all the other trees have all the elements in them. This means that if you do k merges, the cost will be

N - 1   N - 1   N - 1         N - 1
----- + ----- + ----- + ... + -----
K - 1   K - 2   K - 3           1

But this is (n - 1)H(k - 1), where H(k-1) is the (k-1)st harmonic number. This whole expression is then O(n log k), so the total work done while merging is O(n log k).

However, on top of that you have to have some easy way of finding the two smallest trees at each point. This can be done with a priority queue that stores the trees in descending order of size. You'll have k - 1 rounds of doing two dequeues from the tree followed by one enqueue, so the total time for all priority queue operations is O(k log k). This is also O(n log k), so the total runtime for the algorithm is O(n log k).

I'm pretty sure that you can't do much better than this, because you could begin with each of the n nodes in their own AVL tree (k = n). If you could merge any faster than Ω(n log n), then you could sort faster than Ω(n log n) using only comparisons by building the AVL tree formed by merging all the smaller trees, then doing an inorder traversal in O(n) time to sort in better than Ω(n log n), which is known to be impossible.

Hope this helps!