PricingLoginStart free
Forberedelse til kodeinterviews · Lektion

Union by rank og komponenter

Hold træer flade, og tæl grupper

Lektion 2 af 413 trin

Union by rank og komponenter er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Union kan være naiv

En simpel union hænger blot den ene rod under den anden. Hvis det gøres uden omtanke, kan der opstå et højt, langsomt træ, så vi har brug for en smartere måde at sammenføje rødder på.

Hovedidéen

Union efter rang hægter altid det kortere træ under det højere. Ved at holde træerne lave bliver alle senere find-operationer hurtigere. 📏

Hvad rang betyder

Rang er et skøn over et træs højde. Hvert element starter med rang 0, fordi en enkelt node ikke har nogen dybde under sig.

rank = [0] * n

Hægt det kortere under det højere

Sammenlign de to rødder rang. Roden med lavere rang bliver barnet, så det samlede træ forbliver så fladt som muligt.

if rank[ra] < rank[rb]:
    parent[ra] = rb

Lige rang øger rangen

Når begge rødder har samme rang, vælger du en af dem som den nye rod og øger dens rang med én, fordi træet netop blev ét niveau højere.

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Variant: union efter størrelse

Et populært alternativ er union efter størrelse: hægt den mindre mængde under den større. Det er lige så effektivt og giver dig mængdestørrelser uden ekstra arbejde.

Tæl komponenter

Start en tæller på n, fordi hvert element er sin egen gruppe. Hver vellykkede union sammenføjer to grupper til én, så du mindsker tælleren.

components = n

Spring unioner uden effekt over

Hvis to elementer allerede deler en rod, gør union ingenting. Du skal kun mindske tælleren, når deres rødder faktisk er forskellige.

if find(a) != find(b):
    union(a, b)
    components -= 1

Rang plus komprimering

Kombinér union efter rang med stikomprimering, så kører DSU i invers-Ackermann-tid, hvilket reelt er konstant for alle praktiske input. ⚡

Gruppestørrelser efter behov

Med union efter størrelse kan du straks svare på, hvor stor en gruppe er: læs blot den størrelse, der er gemt ved elementets rod.

group = size[find(x)]

Hvornår dette er nyttigt

Optælling af komponenter besvarer klassiske spørgsmål som antal vennekredse eller sammenhængende områder efter en række union-kald. 🌐

Hurtigt tjek

Overvej, hvordan komponenttælleren ændrer sig.

Besvar den i den interaktive lektion

Opsummering

Du lærte union by rank for at holde træerne flade, og hvordan du holder styr på komponentantal og gruppestørrelser. DSU er nu lynhurtig! 🎉

Gratis at komme i gang

Lær Forberedelse til kodeinterviews med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
90
Lektioner
360
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Union by rank og komponenter” gratis?

Ja — hele teksten til “Union by rank og komponenter” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Union by rank og komponenter”?

Hold træer flade, og tæl grupper Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?

Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Hvor lang tid tager lektionen “Union by rank og komponenter”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?

Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. DSU med path compression
  2. Union by rank og komponenter
  3. Kruskals minimum spanning tree
  4. Prims MST med en heap
← Tilbage til Forberedelse til kodeinterviews