Union-Find (Disjoint Set Union) verwaltet eine Partition von Elementen in disjunkte Mengen und unterstützt zwei nahezu-O(1)-Operationen: find (in welcher Menge ist x?) und union (zwei Mengen zusammenführen). Es zeichnet sich bei Konnektivitäts-Abfragen aus.
Die Idee
Jede Menge ist ein Baum mit einem repräsentativen Wurzelknoten. Mit und laufen Operationen in nahezu konstanter Zeit (inverse Ackermann, α(n)).
