Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner. That is to say, you could walk your array from left-to-right building up partial results, and if some asked you to stop after k items you could finish building the tree in log k time (with the total time being O(k), and the extra storage required O(log k).
To state this another way, you could read the data from a pipe and create the tree (via auxilliary structures) without first putting it all in an array first (thereby avoiding the O(n) storage required for the array). Algorithms to do this for red-black trees can be found hidden in the SML NJ library implementation of red-black sets. The theoretical underpinnings can be found in Okasaki's Purely Functional Data Structures.
I have found a similar algorithm for AVL (height-balanced) trees, but I have not (yet) published it, as I don't know whether it is part of the published literature for AVL trees.