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, 10:32): Dynamic Connectivity
  
• Video 4-2 (2026-05-06, 10:31): Dynamische Äquivalenzklassen
  
• Video 4-3 (2026-05-06, 16:51): Quick Find
  
• Video 4-4 (2026-05-06, 14:26): Quick Union
  
• Video 4-5 (2026-05-06, 24:44): Weighted QuickUnion und Pfadkomprimierung
  
• Video 4-6 (2026-05-06, 11:21): Union-Find-Anwendung in Perkolationstheorie
  

Further sources

This chapter is modeled after

• Sedgewick & Wayne, Algorithms, 4th Edition

---

Unit 3  ⋅  Syllabus  ⋅  Unit 5