title: approximated algorithm of union two non-disjoint sets
body: <p><a href="https://stackoverflow.com/questions/3708070/whats-the-best-algorithm-for-non-disjoint-set-union">Whats the best algorithm for Non Disjoint Set Union?</a> is about the precise algorithm of non-disjoint set union.</p>
  <p>With balanced trees, its union cost is n*log(n) where n is the average size of a set; and its membership cost is log(n); the space cost is n if we use balanced trees. With hashmaps, its union cost is O(n), find cost is log(n), and space cost is n.</p>
  <p>My question is if we allow more space, can time cost be smaller?</p>
  <p>A native approach is like this</p>
  <p>If two sets are s1=(a, b) and s2=(b, c), we create a new node s12 whose two children are s1 and s2. Given this, s1 is also a tree with leaves a and b; s2 is similar. So all the sets are like this.</p>
  <pre><code>       s21
         /  \
        s1  s2
       / \  / \
       a b  b c
  </code></pre>
  <p>This is basically a union-find on a non-disjoint set.</p>
  <p>To check is v in a set, we traverse the whole tree of the set. So union's cost is O(1), and find's cost is log(n) on average. But the space cost can be a lot because this way we will be creating a lot of trees for the same set. For example,</p>
  <pre><code>          s
           / \
          s  a
          /\ 
          a a
       
  </code></pre>
  <p>Another native approach would be using a long bit vector to mark which element is used in a set assuming set elements are limited. For example, if my sets can contain only 10k elements, the bit vector's length is 10k, and its i-th bit is 1 iff this element is in the set. With this, set union is turned into a bit vector or. However, this space cost is high for a sparse set, and run time union cost is also same to the number of total possible elements.</p>
  <p>Is there a better (using less space but still getting smaller time cost) approach than these?</p>