I have an input stream of integers coming in an ascending order, my task is to create a balance binary search tree out of that stream, on the fly. I have gone through the link:BBST from a stream of integers and understood that we can make use of Red-Black trees. The thing is, I am looking for more optimal solutions that use 'sorted information' from the input data.
If you use a red-black tree but always start your insertion at the last node inserted, rather than the root, and use a bottom up insertion algorithm, insertion is O(1) amortized. This means constructing the tree will cost O(n), not Ω(n log n).