Algorithmen und Datenstrukturen · Senior · Frage 6 von 75
Was macht Union-Find-Operationen nahezu O(1)?
- 1Jede Menge als sortiertes Array halten
- 2Pfadkompression plus Union by Rank oder Size
- 3Die ganze Struktur nach jeder Vereinigung neu aufbauen
Antwort zeigen
Richtige Antwort: Pfadkompression plus Union by Rank oder Size
Erklärung
Pfadkompression lässt Knoten beim find direkt auf die Wurzel zeigen; Union by Rank hängt den niedrigeren Baum unter den höheren. Zusammen ergibt das amortisiert O(α(n)), wobei α (inverse Ackermann-Funktion) für jedes realistische n unter 5 liegt.