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?
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.