Vereinigung nach Rang und Komponenten

Eine einfache Union hängt eine Wurzel unter eine andere. Bei unvorsichtiger Umsetzung kann dadurch ein hoher, langsamer Baum entstehen. Wir brauchen daher eine klügere Methode zum Zusammenführen von Wurzeln.

Union by rank hängt den kürzeren Baum immer unter den höheren. Flache Bäume machen jedes spätere find schneller. 📏

Rank ist eine Schätzung der Höhe eines Baums. Jedes Element beginnt mit Rang 0, da ein einzelner Knoten keine darunterliegende Tiefe besitzt.

Vergleichen Sie die Ränge der beiden Wurzeln. Die Wurzel mit dem kleineren Rang wird zum Kind, damit der kombinierte Baum möglichst flach bleibt.

Wenn beide Wurzeln den gleichen Rang haben, wählen Sie eine beliebige als neue Wurzel und erhöhen ihren Rang um 1, da der Baum gerade um eine Ebene gewachsen ist.

Eine beliebte Alternative ist union by size: Hängen Sie die kleinere Menge unter die größere. Das ist ebenso effektiv und liefert die Gruppengrößen kostenlos mit.

Beginnen Sie mit einer Anzahl von n, da jedes Element seine eigene Gruppe bildet. Jede erfolgreiche Union verbindet zwei Gruppen zu einer, also verringern Sie die Anzahl.

Wenn zwei Elemente bereits dieselbe Wurzel haben, bewirkt die Union nichts. Verringern Sie die Anzahl nur, wenn sich ihre Wurzeln tatsächlich unterscheiden.

Kombinieren Sie union by rank mit Pfadkompression, dann läuft DSU in inverser Ackermannzeit – für jede Eingabe aus der Praxis effektiv konstant. ⚡

Mit union by size können Sie die Größe jeder Gruppe sofort abfragen: Lesen Sie einfach die am Wurzelknoten des Elements gespeicherte size aus.

Das Zählen von Zusammenhangskomponenten beantwortet klassische Fragen wie die Anzahl von Freundeskreisen oder zusammenhängenden Bereichen nach einer Folge von union-Aufrufen. 🌐

Sie haben union by rank gelernt, um Bäume flach zu halten, und wie Sie die Anzahl der Komponenten und Gruppengrößen verfolgen. DSU ist jetzt extrem schnell! 🎉