OK, so some of the people here actually learned computer science during 
their computer science qualification. (Unlike me, who only learned IT. :-P )

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?

Obviously if all the elements of one set are larger than the elements of 
the other, we can just bolt the two trees together (although it might be 
necessary to rebalance, and you need to find a root element from somewhere).

Consider, for example, the two trees:

    |       |
    3       4
   / \     / \
  1   5   2   6

The union of these is

      4
     / \
    2   5
   / \   \
  1   3   6

(Alternatively, 3 can be the root, yielding a mirror image of the above 
tree.)

I'm not seeing any way of building this result that's faster than just 
repeatedly inserting the elements of one tree into the other and 
rebalancing.

I see two possibilities:

- I'm too stupid to see the shortcut.

- There /is/ not shortcut.

Does anyone know the answer? (I'm sure there's something in Knuth. :-P )

Post a reply to this message