DSU med sökvägskomprimering
Find och union på nästan konstant tid
DSU med sökvägskomprimering är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad en DSU håller reda på
En Disjoint Set Union håller objekt grupperade i överlappningsfria mängder, så att Ni kan fråga om två saker redan hör ihop. 🤝
Mängder som träd
DSU lagrar varje mängd som ett träd. Varje element pekar på en förälder, och den översta noden, roten, är det unika namnet på hela gruppen.
Föräldraarrayen
Ni lagrar alla dessa länkar i en array. Börja med varje element som sin egen förälder, vilket betyder att varje objekt från början ligger i en egen mängd.
parent = list(range(n))Hitta roten
Operationen find följer föräldralänkarna uppåt tills ett element pekar på sig självt. Denna självrefererande nod är roten som identifierar mängden.
while parent[x] != x:
x = parent[x]Långa kedjor är problematiska
Utan försiktighet kan mängder bilda långa, smala kedjor. Då får find gå nod för nod och en enda fråga kan kosta O(n), vilket är alldeles för långsamt.
Här kommer path compression
Path compression löser detta: medan Ni hittar roten pekar Ni om varje besökt nod direkt på roten, så att trädet plattas ut till nästa gång. ⚡
Rekursiv komprimering
Det renaste sättet är rekursion. Hitta roten och lagra den sedan i parent[x] innan Ni returnerar, så att länken förkortas permanent.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Två objekt, samma mängd?
För att testa om två element är sammanbundna jämför Ni deras rötter. Om find(a) equals find(b) ligger de i samma grupp; annars är de fortfarande åtskilda.
if find(a) == find(b):
print("connected")Slå ihop två mängder
Operationen union förenar grupper genom att låta den ena roten peka på den andra. En enda rad länkar ihop två hela träd till en mängd.
def union(a, b):
parent[find(a)] = find(b)Varför det är så snabbt
Med endast komprimering körs operationerna ungefär på O(log n) amorterad tid, och tillsammans med rangordning når de nästan konstant tid per fråga.
Där DSU glänser
DSU är utmärkt för frågor om konnektivitet: vänkretsar, nätverkskomponenter och Kruskals uppspännande träd bygger alla på snabba find- och union-operationer. 🌐
Snabb kontroll
Tänk på vad path compression faktiskt ändrar.
Sammanfattning
Ni byggde en DSU: en föräldraarray, find för att hitta roten och union för att slå ihop mängder. Path compression håller den blixtsnabb. Bra jobbat! 🎉
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”DSU med sökvägskomprimering” gratis?
Ja – hela texten till ”DSU med sökvägskomprimering” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”DSU med sökvägskomprimering”?
Find och union på nästan konstant tid Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”DSU med sökvägskomprimering”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- DSU med sökvägskomprimering
- Union by rank och komponenter
- Kruskals minimala uppspännande träd
- Prims MST med en heap