Merging AVL trees using an empty tree (C++ templates)

As part of an AVL template I am working on (C++ templates) I was trying to merge 2 AVL trees in O(n1+n2开发者_如何学Go) complexity when n1+n2 is the total elements in both trees.

I thought about the next algorithm.

1. Inorder traversal on the 1st tree and build an array/list - O(n1)
2. Inorder traversal on the 2nd tree and build an array/list - O(n2)
3. Merge sort of those 2 arrays and build final sorted array/list in the size of n1+n2 - O(n1+n2)
4. Build an empty almost complete binary tree with n1+n2 vertices - O(n1+n2).
5. Inorder traversal on that almost complete binary tree while updating the vertices with the elemets in the merged array/list.

My question is how do I actually build the empty almost complete binary tree with n1+n2 vertices?

If the nodes issue by the merge sort are stored in a vector, it can be done relatively easily. Your nodes are already sorted, so you can "insert" the nodes in the following fashion:

1. Build your root node from the element at 1/2 of the array;
2. Build the root's child nodes using the elements at 1/4 and 3/4 of the array;
3. Repeat 2 recursively.

This should feel to you as an in-order traversal of a binary tree that happens to be represented as a sorted array.

Note that for this to work, you need to build the tree with balancing "turned off". This is most likely going to require you to make this a private method of your class, probably a special constructor.