# Union-find approach - weighted quick-union

**Weighted quick-union**is a modification to quick-union that helps by avoiding the problem of tall trees- track the size of each tree (number of objects)
- balance by linking the root of the smaller tree to the root of the larger tree (union by size on a disjoint-set)
- alternatively use union by height/rank

## Example implementation

The only difference between this and quick-union is the addition of the `sz[]`

array, which counts the number of objects in the tree rooted at `i`

```
public class WeightedQuickUnionUF
{
private int[] id;
private int[] sz;
public WeightedQuickUnionUF(int N)
{
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
sz[i] = 1;
}
}
private int root(int i)
{
while(i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
if (i == j) return;
if (sz[i] < sz[j])
{
id[i] = j;
sz[j] += sz[i];
} else
{
id[j] = i;
sz[i] += sz[j];
}
}
}
```

- This approach improves upon quick-union:
`Find`

: time is proportional to depth of`p`

and`q`

`Union`

: constant time, given roots

- the depth of the tree will always be equal to or less than
`log2 N`

Cost:

`new`

:`N`

`Union`

:`log2 N`

(including cost of finding roots)`Find`

:`log2 N`

## Another improvement: path compression

- upon computing
`root(p)`

, simply set the`id`

of each visited node to point to that root - this lets us circumvent the internal cost of
`root()`

by essentially memoizing the operation - Implementations:
- “two-pass”:
- add second loop to
`root()`

to set the`id[]`

of each visited node to the root

- add second loop to
- “one-pass” (simpler):
- make every other node in the path point to its grandparent (cuts the path length in half)

- “two-pass”:
- both implementations let us keep the tree flat, which makes things easier
- cost is improved
**dramatically**to near linear-time- with path-compression, weighted quick-union allows 10^9 unions on 10^9 objects to be executed in 6 seconds
- shows the value of a good algorithm!

- with path-compression, weighted quick-union allows 10^9 unions on 10^9 objects to be executed in 6 seconds