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 (which is
necessary because if you don't, it won't be a valid *search* tree anymore,
where every subnode on the left of a node will be smaller or equal to the
node, and each subnode on the right will be larger or equal to the node),
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). 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).

  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.)

-- 
                                                          - Warp

Post a reply to this message