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?