Informatik Datenstrukturen – Union-Find und Zusammenhang
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was verwaltet die Union-Find-Datenstruktur? · Welche zwei Grundoperationen bietet Uni…
Karten
14 KartenWas verwaltet die Union-Find-Datenstruktur?
Rückseite
Sie verwaltet eine Partition einer Menge in disjunkte Teilmengen und unterstützt Operationen zum Zusammenführen und Auffinden der Repräsentanten.
Welche zwei Grundoperationen bietet Union-Find an?
Rückseite
Find(x) liefert den Repräsentanten der Menge, die x enthält; Union(x, y) vereint die Mengen, die x und y enthalten.
Wie wird die Menge eines Elements im Find-Algorithmus bestimmt?
Rückseite
Man folgt den Elternzeigern vom Element bis zur Wurzel, die sich selbst als Elternteil referenziert – diese Wurzel ist der Repräsentant.
Was bewirkt Path Compression bei der Find-Operation?
Rückseite
Alle besuchten Knoten auf dem Pfad zur Wurzel werden direkt mit der Wurzel verknüpft, wodurch spätere Find-Aufrufe beschleunigt werden.
Was bedeutet Union by Rank?
Rückseite
Der Baum mit kleinerem Rang (Höhenapproximation) wird unter den Baum mit größerem Rang gehängt, um die Baumhöhe minimal zu halten.
Was ist der Unterschied zwischen Union by Rank und Union by Size?
Rückseite
Union by Rank nutzt eine obere Schranke der Baumhöhe, Union by Size die exakte Knotenzahl; beide garantieren logarithmische Höhe ohne Path Compression.
Wie lautet die amortisierte Laufzeit von Find und Union mit beiden Optimierungen?
Rückseite
O(α(n)) pro Operation, wobei α die inverse Ackermann-Funktion ist – für alle praktischen Eingabegrößen ≤ 4.
Wofür steht α(n) in der Laufzeitanalyse von Union-Find?
Rückseite
Die inverse Ackermann-Funktion, die extrem langsam wächst; für n ≤ 2^65536 gilt α(n) ≤ 4.
Wie erkennt man mit Union-Find einen Zyklus in einem ungerichteten Graphen?
Rückseite
Für jede Kante (u,v): Falls Find(u) == Find(v), schließt die Kante einen Zyklus; andernfalls Union(u,v).
Welche Rolle spielt Union-Find im Kruskal-Algorithmus?
Rückseite
Er prüft bei jeder Kante in Gewichtssortierung, ob ihre Endpunkte bereits im gleichen Baum liegen (Zyklus), und fügt sie sonst zum MST hinzu.
Wie initialisiert man Union-Find für n Elemente?
Rückseite
Jedes Element wird zur eigenen Menge: parent[i] = i, rank[i] = 0 (oder size[i] = 1).
Was ist der Repräsentant einer Menge in Union-Find?
Rückseite
Die Wurzel des zugehörigen Baums, die sich selbst als Elternteil hat; alle Elemente der Menge zeigen direkt oder indirekt auf sie.
Warum funktioniert Path Compression nicht rekursiv ohne Stack-Überlauf bei großen n?
Rückseite
Rekursionstiefe entspricht Baumhöhe; ohne Path Compression kann diese Θ(n) betragen. Iterative Implementierung vermeidet Stack-Probleme.
Wann sind zwei Elemente in derselben Zusammenhaltskomponente?
Rückseite
Genau dann, wenn Find(x) == Find(y) gilt – beide haben denselben Repräsentanten in der Union-Find-Struktur.