Union-Find

1. Dynamic Connectivity Problem :

    a)  Union command : connect two objects

    b)  Find/connected query: is there a path connecting the two objects?

 

2. Quick-find

    a) Integer array id[] of size N

    b) Interpretation: p and q are connected iff they have the same id.

    c) Find: Check if p and q have the same id.

    d) Union : To merge components containing p and q, change all entries whose id equals id[p] to id[q].

    Find is quick which only takes 2 array access. Union is expensive , it cost N array access and N union will cost N^2

 

3. Quick-union

    a) Integer array id[] of size N.
    b) Interpretation: id[i] is parent of i.
    c)  Root of i is id[id[id[...id[i]...]]].

    d)  Find: Check if p and q have the same root.

    e)  Union: To merge components containing p and q, set the id of p's root to the id of q's root.

    Both Union and Find can be expensive in worst case.

 

4.  Quick-find defect:
    a) Union too expensive (N array accesses).
    b) Trees are flat, but too expensive to keep them flat.

      Quick-union defect.
    a) Trees can get tall.
    b) Find too expensive (could be N array accesses).

 

5.  Weighted quick-union.
    a)  Modify quick-union to avoid tall trees.
    b)  Keep track of size of each tree (number of objects).
    c)  Balance by linking root of smaller tree to root of larger tree.

    Proposition: Depth of any node x is at most lg N.

    Pf. When does depth of x increase?
    Increases by 1 when tree T1 containing x is merged into another tree T2.
      1)  The size of the tree containing x at least doubles since | T 2 | ≥ | T 1 |.
      2)  Size of tree containing x can double at most lg N times. (the total # of nodes is at most N)

 

6.  Quick union with path compression: Just after computing the root of p, set the id of each examined node to point to that root.

    Two-pass implementation: add second loop to root() to set the id[] of each examined node to the root.
    Simpler one-pass variant: Make every other node in path point to its grandparent (thereby halving path length).