Union-Find-Struktur
# 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, welches als Name der Menge dient. Union vereinigt zwei solche Mengen, Find(x) bestimmt das kanonische Element derjenigen Menge, die x enthält, und Make-Set erzeugt eine Elementarmenge {x} mit dem kanonischen Element x.

## Definition

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

    $S=X_{0}\uplus X_{1}\uplus X_{2}\uplus \ldots \uplus 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($x$, $y$): Hängt die Wurzel des niedrigeren Baumes als neues Kind unter die Wurzel des höheren Baumes (gewichtete Vereinigung). Falls nun $x$ Kind von $y$ ist, werden $x$ und $y$ vertauscht.
* Find($x$): Wandert vom Knoten $x$ aus den Pfad innerhalb des Baumes nach oben bis zur Wurzel und gibt diese als Ergebnis zurück.

## Heuristiken

Um die Operationen Find und Union zu beschleunigen, gibt es die Heuristiken union by size, union by rank (Rang- und Größenheuristik) und Pfadkompression, wobei sich union by size und union by rank gegenseitig ausschließen und union by rank oft in Kombination mit Pfadkompression verwendet wird.

### Union by size

Bei der Operation Union(r,s) wird der Baum, der in Summe weniger Knoten hat, sprich kleiner ist, unter den größeren Baum gehängt. Damit verhindert man, dass einzelne Teilbäume zu Listen entarten können wie bei der naiven Implementation (r wird in jedem Fall Wurzel des neuen Teilbaums). Die Tiefe eines Teilbaums T kann damit nicht größer als $\log \left|T\right|$ werden. Mit dieser Heuristik verringert sich die Worst-Case-Laufzeit von Find von $O(n)$ auf $O(\log n)$. Für eine effiziente Implementation führt man bei jeder Wurzel die Anzahl der Elemente im Teilbaum mit.

### Union by rank

Wird ausschließlich die Heuristik union by rank verwendet, entspricht der Rang (rank) einer Wurzel der Höhe ihres Unterbaumes. Es wird stets der Baum mit dem niedrigeren Rang dem mit dem höheren angehängt. Bei gleichem Rang kann die Verkettung der Bäume beliebig gewählt werden. Somit kann der Rang eines Knoten nur wachsen, wenn zwei Bäume des gleichen Rangs aneinander gehängt werden.

Daraus folgt insbesondere:

* Knoten ohne Kinder haben den Rang 0
* Wenn die zu kombinierenden Bäume den gleichen Rang haben, ist der Rang der resultierenden Baumes um 1 größer

Man kann zur weiteren Effizienzsteigerung union by rank in Kombination mit Pfadkompression verwenden. In diesem Fall wird deutlich, weshalb die Bezeichnung des Rangs anstelle der der Tiefe verwendet wird: Die Pfadkompression verringert die Höhe von Bäumen, während ihr Rang bestehen bleibt. Siehe auch Pfadkompression.

### 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 (Wegkompression)**

Nach dem Ausführen von Find(x) werden alle Knoten auf dem Pfad von x zur Wurzel direkt unter die Wurzel gesetzt. Man beachte hierbei, dass die Operation Union(x,y) die Operation Find(x) verwendet. Dieses Verfahren bringt im Vergleich zu den beiden folgenden den größten Kostenvorteil für nachfolgende Aufrufe von Find für einen Knoten im gleichen Teilbaum. Zwar muss dabei jeder Knoten auf dem Pfad zwischen Wurzel und x zweimal betrachtet werden, für die asymptotische Laufzeit ist das jedoch egal.

## 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 Laufzeiten ($n=\left|S\right|$):

Triviale Implementierung mit einem Array A (A[i] = x: Knoten i liegt in der Menge x), worst-case: Find $O(1)$, Union: $O(n)$

Implementierung mit Bäumen:

* ohne Heuristiken: Find $O(n)$, Union $O(n)$
* mit Union-By-Size, worst-case: Find $O(\log(n))$, Union $O(1)$
* mit Union-By-Size, Pfadkompression, worst-case: Find $O(\log(n))$, Union $O(1)$
* mit Union-By-Size, Pfadkompression, Folge von m Find- und n-1 Union-Operationen: $O\left(n+m\cdot \alpha (n)\right)$

Dabei ist $\alpha (n)$ die Umkehrfunktion der Ackermannfunktion $A(n,n)$. Sie wächst sehr langsam und ist für alle „praktischen“ Eingaben ($n<10^{80}$) kleiner als 5. Im Jahr 1977 hat Robert Tarjan gezeigt, dass für eine Sequenz m Find- und n-1 Union-Operationen jede Datenstruktur im Pointer-Maschinen Modell eine Laufzeit von $\Omega \left(n+m\cdot \alpha (n)\right)$ benötigt. Fredman und Saks haben 1989 gezeigt, dass diese untere Schranke auch im allgemeineren Cell-Probe Modell gilt. Daraus folgt, dass die Datenstruktur mit Union-By-Size und Pfadkompression eine asymptotisch optimale Laufzeit besitzt, und es keine Union-Find-Datenstruktur geben kann, die sowohl Find als auch Union amortisiert in O(1) ausführt.

## Anwendungen

Union-Find-Strukturen eignen sich gut, um Zusammenhangskomponenten von Graphen zu verwalten.

Union-Find-Strukturen können auch genutzt werden, um effizient herauszufinden, ob ein Graph Zyklen enthält.

Das folgende Computerprogramm in der Programmiersprache C++ zeigt die Implementierung eines ungerichteten Graphen mit einem Array von Kanten. Der ungerichtete Graph wird als Datentyp UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode main verwendet, das auf der Konsole ausgibt, ob der gegebene Graph Zyklen enthält. Die Funktion unionSubsets verwendet union by rank, um zwei Teilmengen von Kanten des Graphen zu vereinigen.

Der Algorithmus von Kruskal erfordert beispielsweise eine solche Datenstruktur, um effizient implementiert werden zu können.

