# Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional storage, and only O(log n)-time after then end-of-stream is discovered. The technique involves pennants and the 1-2 binary representation of n.

The technique needs to be modified for AVL trees, and I haven't seen referneces to an on-line algorithm for creating AVL trees. Does anyone know of such a published algorithm?

• Do you have a citation for the claim about red-black trees? Do the items arrive in sorted order? – jbapple Jun 12 '14 at 0:51

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that location.