Le 31/01/2012 10:23, Invisible a écrit :
> 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...)


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)

Post a reply to this message