Union Find Note

Quick-Find Solution

• Quick-Find algorithm is too slow and may take ~MN steps to process M union commands on N objects.
• Trees are flat, but too expensive to keep them flat.

public class QuickFind {
	private int[] id;

	public QuickFind(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
		}
	}

	public boolean find(int p, int q) {
		return id[p] == id[q];
	}

	public void unite(int p, int q) {
		int pid = id[p];
		for (int i = 0; i < id.length; i++) {
			if (id[i] == pid) {
				id[i] = id[q];
			}
		}
	}
}

The complexity:

Union N

Find 1

Quick-union (lazy approach)

• Find. Check if p and q have the same root.
• Union. Set the id of q's root to the id of p's root

Defect:

• Trees can get tall.
• Find too expensive (could be N steps)
• Need to do find to do union.

Complexity:

Union N (*includes cost of find)

Find N (worst case)

public class QuickUnion {
	private int[] id;

	public QuickUnion(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
		}
	}

	private int root(int i) {
		while (i != id[i]) {
			i = id[i];
		}

		return i;
	}

	public boolean find(int p, int q) {
		return root(p) == root(q);
	}

	public void unite(int p, int q) {
		int i = root(p);
		int j = root(q);
		id[i] = j;
	}
}

Improvement

Improvement 1: Weighted quick-union

• Modify quick-union to avoid tall trees.

• Keep track of size of each component.

• Balance by linking small tee below large one.