On 30/01/2012 05:08 PM, Kevin Wampler wrote:

> I don't follow this reasoning, since you only need the resulting tree to
> be a valid BST at the end of the computation, but it can take any
> convenient state when you're adding the individual elements. For
> instance is there some reason why the following algorithm sketch doesn't
> work?
>
> 1) Flatten BSTs into sorted arrays / linked lists O(n+m)
> 2) Merge arrays O(n+m)
> 3) Rebuild BST from sorted array O(m+n)
>
> That should give you O(m+n) time to perform the union, which is better
> than Andrew's suggestion.

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?

(I can kind of see how that would work if the data is in an array; 
arrays support random access, so you could just binary chop the array 
and keep the results as a BST. I'm trying to figure out if you can do 
anything with a linked list, which does /not/ support random access...)

Post a reply to this message