Path compression improves repeated operations on a disjoint-set forest by redirecting nodes encountered during findPartition toward the current set representative. It is inexpensive to implement and complements tree balancing by rank. section 5.6 section 5.6.1
A compressed find operation proceeds as follows:
- Follow parent or root links from the requested element until reaching the tree root. section 5.6.1
- Retrace the same path and make each encountered node point directly to the root. section 5.6.1
- Return the representative; later finds on that path can reach it in one step. section 5.6.1
- Combine the heuristic with rank-based balancing so merge attaches the smaller-rank tree beneath the larger-rank root. section 5.6.2
Compressing a stale path
If findPartition(6) climbs through elements 9 and 6 before reaching the root, it backtracks and updates both elements. Future searches through either node use the shortened route. section 5.6.1
Figure 5.12 Call to find on the same disjoint set of figure 5.11. Notice that the dark blue tree is out of sync. If we call find on the element 6, the algorithm starts slowly crawling up the blue tree, until it finds its root (third diagram). Then (bottom diagrams), the algorithm backtracks, updating the root for the intermediate elements 9 and 6.
The figure traces find on element 6 from an out-of-sync tree to the root, then shows root-pointer updates for intermediate nodes. section 5.6.1
