Improvement 2: Path Compression

  • Trace the Quick Union implementation with path-compression heuristic.
  • Explain the runtime improvements gained by using the heuristic for union-find operations.

After computing the root of pp, set the ID of each examined node to point to that root.

For example, consider the following tree:

Assume we perform find(J) operation. On our way to find the root, we would pass through II, FF, BB until we get to AA, the root.

We could set all these vertices to directly point to the root, so the tree becomes shallower:

The heuristic described above is known as path compression.