Unit 4: Case Study: Union-Find

This unit gives a first show-case of how clever data structure design can dramatically improve the efficiency of an algorithm.

• Disjoint Set ADT
• quick-find
• quick-union
• weighted quick-union
• path compression

Material

• slides

• lecture notes

• Video 4-1 (2026-05-04): Dynamic Connectivity

• Video 4-2 (2026-05-06): Dynamische Äquivalenzklassen

• Video 4-3 (2026-05-06): Quick Find

• Video 4-4 (2026-05-06): Quick Union

• Video 4-5 (2026-05-06): Weighted QuickUnion und Pfadkomprimierung

• Video 4-6 (2026-05-06): Union-Find-Anwendung in Perkolationstheorie

Further sources

This chapter is modeled after

• Sedgewick & Wayne, Algorithms, 4th Edition

---

Unit 3  ⋅  Syllabus  ⋅  Unit 5