How to create an AVL Tree from ArrayList of values in O(n) time?

Question

My assignment is to create an AVL Tree from a sorted array list of values in O(n) time where n is the number of values

I have been working on this but I cannot get O(n) time, the best I can get is O(nlog(n))

My problem is that every time a node that causes the tree to be unbalanced is inserted, I have to do another loop to find the node that is unbalanced and apply rotation(s) to balance the tree again.

Any help is greatly appreciated, thanks!

Answer 1

Inserting is O(logn), so true, nobody can do better than O(nlogn) when inserting. Really, you shouldn't insert into the AVL-tree. You should just create the tree. Create all the nodes and pick the values from the array as you are constructing new nodes. Don't find/search the value you need, just take it, the array is sorted.

Given a list that contains 5 elements and is sorted, for example [1,2,3,4,5], what would be the root of the tree? How about for 7 elements? 10? ...?

After you got the root, then what would be the root of the left subtree. What's the list to look at? Which part of the list do you have to store in the left subtree?

That's all.

Answer 2

How about just creating a complete balanced tree, with a few nodes at the lowest level possibly missing, e.g., for 6 elements, create

      o
    /   \
   o     o
  / \    /
 o   o  o

Then do an inorder walk, and when you visit the i-th node, set its key to A[i].

This is a valid AVL tree, since every node has a left and right child whose heights differ by at most one.

The original tree can be constructed in O(n), and the inorder walk in O(n), so the complexity is O(n).

Incidentally, on a semirelated note, there's a technique called heapify for building a heap (mix or max) out of an array of integers that's O(n) for a length n array, even though the insertion into a heap is O(log n) - the trick is to do it bottom up.