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

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.