CSCI2100 · Theorem · Chapter 1 · Disjoint sets
Path compression preserves the partition
3 steps of prerequisites below it
Redirecting the visited elements to their root leaves every element with the same root, so the represented partition and the root size counters are unchanged.
Taught in
Uses
- Parent forest · used in its proof, proof step 1.1
- Path compression · used in its definition, passage 1.1
Used by
No later knowledge point in these notes uses it.
Everything this builds on, earliest first · 3 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Partition · 1.1
- Parent forest · 1.1
- Path compression · 1.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.