In this lecture, we discuss some approaches to implementing Disjoint Sets Union. After ruling out a couple of naive approaches, we describe the heuristics of:
Union by depth, and
Path compression + union by rank
We do not prove the theoretical guarantees promised by these approaches. If you are interested in the proofs, please refer to this book chapter by Jeff Erickson:
[ Ссылка ]
If you are watching this during an active run of the course, you can join the discord community for the course using this link:
[ Ссылка ]
The course website can be found at:
[ Ссылка ]
