Union-Find-Struktur

Eine Union-Find-Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make-Set} gebildet. Union-Find-Strukturen dienen zur Verwaltung von Zerlegungen in disjunkte Mengen. Dabei bekommt jede Menge der Zerlegung ein kanonisches Element zugeordnet, dieses dient als Name der Menge. Union vereinigt zwei solche Mengen, Find(x) bestimmt das kanonische Element derjenigen Menge, die x enthält und Make- Set erzeugt eine Einermenge {x} mit dem kanonischen Element x.

Definition

Eine endliche Menge $S$ sei in die disjunkten Klassen $X_{i}$ partitioniert:

$S=X_{0}\cup X_{1}\cup X_{2}\cup \ldots \cup X_{k}$ mit $X_{i}\cap X_{j}=\varnothing \quad \forall i,j\in \lbrace 0,1,\ldots ,k\rbrace ,i\neq j$.

Zu jeder Klasse $X_{i}$ wird ein Repräsentant $r_{i}\in X_{i}$ ausgewählt. Die zugehörige Union-Find-Struktur unterstützt die folgenden Operationen effizient:

• Init($S$): Initialisiert die Struktur und bildet für jedes $x\in S$ eine eigene Klasse mit $x$ als Repräsentant.
• Union($r$, $s$): Vereinigt die beiden Klassen, die zu den beiden Repräsentanten $r$ und $s$ gehören, und bestimmt $r$ zum neuen Repräsentanten der neuen Klasse.
• Find($x$): Bestimmt zu $x\in S$ den eindeutigen Repräsentanten, zu dessen Klasse $x$ gehört.

Implementierung

Eine triviale Implementierung speichert die Zugehörigkeiten zwischen den Elementen aus $S$ und den Repräsentanten $r_{i}$ in einem Array. Für kürzere Laufzeiten werden jedoch in der Praxis Mengen von Bäumen verwendet. Dabei werden die Repräsentanten in den Wurzeln der Bäume gespeichert, die anderen Elemente der jeweiligen Klasse in den Knoten darunter.

• Union($r$, $s$): Hängt die Wurzel des niedrigeren Baumes als neues Kind unter die Wurzel des höheren Baumes (gewichtete Vereinigung). Falls nun $r$ Kind von $s$ ist, werden $r$ und $s$ vertauscht. Für eine effiziente Implementierung werden die Baumhöhen in den Wurzeln mitgeführt.
• Find($x$): Wandert vom Knoten $x$ aus den Pfad innerhalb des Baumes nach oben bis zur Wurzel und gibt diese als Ergebnis zurück.

Pfadkompression

Um spätere Find($x$) Suchvorgänge zu beschleunigen, versucht man die Wege vom besuchten Knoten zur zugehörigen Wurzel zu verkürzen.

- maximale Verkürzung

Nach dem Ausführen von Find($x$) werden alle Knoten auf dem Pfad von $x$ zur Wurzel direkt unter die Wurzel gesetzt.

Da man aber doppelte Durchläufe in dem Baum vermeiden will, sind folgende Verfahren geeigneter:

- Aufteilungsmethode (splitting)

Während des Durchlaufes lässt man jeden Knoten auf seinen bisherigen Großvater zeigen (falls vorhanden); damit wird ein durchlaufender Pfad in zwei der halben Länge zerlegt.

- Halbierungsmethode (halving)

Während des Durchlaufes lässt man jeden zweiten Knoten auf seinen bisherigen Großvater zeigen.

Diese Methoden haben beide dieselben amortisierten Kosten wie die oberste Kompressionsmethode (Knoten unter die Wurzel schreiben). Alle Kompressionsmethoden beschleunigen zukünftige Find($x$)-Operationen.

Laufzeiten

Union-Find-Datenstrukturen ermöglichen die Ausführung der obigen Operationen mit den folgenden Zeitkomplexitäten:

Triviale Implementierung: $O(\vert S\vert )$

Implementierung mit Bäumen ($n=\vert S\vert$):

• mit gewichteter Vereinigung: Union $O(1)$, Find $O(log(n))$
• mit gewichteter Vereinigung, Pfadkompression, worst-case (Find und Union): $\Theta (log(n))$
• mit gewichteter Vereinigung, Pfadkompression, Folge von m Operationen (Find und Union): $O(m(log(n))*)$