Union by rank en componenten

Een eenvoudige union hangt de ene wortel onder de andere. Als je dit onzorgvuldig doet, kan er een hoge, trage boom ontstaan. Daarom hebben we een slimmere manier nodig om wortels samen te voegen.

Union op basis van rang hangt de kortere boom altijd onder de hogere. Door de bomen ondiep te houden, wordt elke volgende find sneller. 📏

Rang is een schatting van de hoogte van een boom. Elk element begint met rang 0, omdat een enkele knoop geen diepte onder zich heeft.

Vergelijk de rangen van de twee wortels. De wortel met de lagere rang wordt het kind, zodat de gecombineerde boom zo vlak mogelijk blijft.

Als beide wortels een gelijke rang hebben, kies je een van beide als nieuwe wortel en verhoog je diens rang met één, omdat de boom één niveau hoger is geworden.

Een populair alternatief is union op basis van grootte: hang de kleinere verzameling onder de grotere. Dit werkt net zo goed en levert de groepsgroottes er gratis bij.

Begin het aantal op n, omdat elk element zijn eigen groep is. Elke geslaagde union voegt twee groepen samen, dus verlaag je het aantal.

Als twee elementen al dezelfde wortel hebben, doet union niets. Verlaag het aantal alleen als hun wortels echt verschillen.

Combineer union op basis van rang met padcompressie en DSU werkt in inverse-Ackermann-tijd, die voor elke realistische invoer praktisch constant is. ⚡

Met union op basis van grootte kun je onmiddellijk bepalen hoe groot elke groep is: lees gewoon de grootte af die bij de wortel van het element is opgeslagen.

Het tellen van componenten beantwoordt klassieke vragen, zoals hoeveel vriendengroepen of verbonden gebieden er zijn na een reeks aanroepen van union. 🌐

Je hebt union by rank geleerd om bomen plat te houden en te tellen hoeveel componenten en hoe grote groepen er zijn. DSU is nu razendsnel! 🎉