>> Question: If you have a bunch of data in sorted order, how do you build
>> a BST from that faster than O(n log n) times?
>
> Use a model BST, filled with 1 to n+m. (or whatever please you, you just
> need n+m values)
>
> Then run in order through the BST, and replace each element with the top
> of the list that you remove. (it's not the BST traditional replace
> (which might rebalance), just a basic substitution)

By "in order", I presume you mean from smallest to greatest, rather than 
(say) from the top of the tree to the bottom?

Seems to me you need to know the size of the tree before hand.

Notice that if we have two arbitrary sets S and T, then

   |S| min |T| <= |S union T| <= |S| + |T|

In other words, we don't know the size of the result set until we 
actually construct it.

Is there some way to build the resulting tree incrementally, if you 
don't know what its final size should be? (I'm guessing "no", if only 
because the result tree needs to be balanced...)

Post a reply to this message