Union-Find

Kurz: Union-Find verwaltet Gruppen von Elementen und beantwortet sehr schnell, ob zwei Elemente zur selben Gruppe gehören und wie man zwei Gruppen vereint.

Genauer: Jede Gruppe wird als Baum gespeichert, dessen Wurzel die Gruppe vertritt. find(x) folgt den Eltern bis zur Wurzel, union(a, b) hängt eine Wurzel unter die andere.

Im Detail

• Pfadkompression: Bei find werden besuchte Knoten direkt unter die Wurzel gehängt. Spätere Suchen sind dadurch fast sofort.
• Union by Rank/Size: Der kleinere Baum kommt unter den größeren, damit Bäume flach bleiben.
• Laufzeit: Praktisch konstant (inverse Ackermann-Funktion) pro Operation.
• Einsatz: Zusammenhangskomponenten, Kruskals Algorithmus für minimale Spannbäume, Zyklen in ungerichteten Graphen erkennen.
• Grenze: Gruppen lassen sich vereinen, aber nicht wieder trennen.

Siehe auch: Graph (Datenstruktur)