On 1/30/2012 8:22 AM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> I'm using binary search trees to implement sets. My question is this: Is
>> there a way to compute a set union, faster than just inserting all the
>> elements of one set into the other set?
>
>     From a computational complexity point of view, no. Rationale: Every time
> you insert an element to the tree, the tree has to be re-balanced

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.

Post a reply to this message