On 30/01/2012 04:22 PM, 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.

Well, at least that means it's not that I'm just too stupid to find 
it... :-}

> Rationale: Every time
> you insert an element to the tree, the tree has to be re-balanced (which is
> necessary because if you don't, it won't be a valid *search* tree anymore,

You seem to be confusing balance and validity.

A tree is a valid binary search tree if all the values in the left 
subtree are lower, and all the values in the right subtree are higher. 
That's quite trivial to achieve. A tree is *balanced* if both subtrees 
are roughly the right size - and an unbalanced tree usually means lower 
performance. (Depending on what you want to do to it. Certainly this is 
the case for a BST.)

> and the fastest you can re-balance a tree is O(log n). Hence the worst case
> scenario for inserting one tree into another is O(n log n).

Right, OK.

> There may be
> best-case scenarios where a particular tree could be inserted in a particular
> other tree faster, but that doesn't change the upper bound (for the worst
> case scenario, and probably not even for the average scenario).

Fewer tree manipulations, in exchange for more decision processing. 
Looks like it probably wouldn't come out any faster.

>    While the computational complexity cannot be reduced, if you are looking
> at reducing the constant factor (what's colloquially called "hacker
> optimization") then you could probably traverse both trees from smallest
> to largest nodes linearly, and insert from one tree to the other as
> needed. Since in each insertion you don't need to perform a full search
> starting from the root node, it might be slightly faster by some constant
> factor. (The rebalancing still adds the O(log n) complexity to each
> insertion, though, even if you find a way to insert more than one node
> with one single re-balancing in some cases.)

Hmm, OK... I'll see what I can come up with.

Presumably set intersection can't easily be accelerated either?

Post a reply to this message