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? 
Are there published algorithms for on-line creation of AVL trees from ordered streams?
ds.algorithms;ds.data structures;online algorithms;binary trees