Union etter rang og den inverse Ackermann-grensen
Legg til union basert på rang for å holde trærne flate, og forstå hvorfor de kombinerte optimaliseringene gir amortisert O(alpha(n))-tid – i praksis konstant tid.
Union etter rang og den inverse Ackermann-grensen er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hvorfor trær blir høye uten rang
Vanlig path compression hindrer høye trær etter traverseringer, men under de første union-operasjonene kan vi fortsatt bygge et høyt tre hvis vi alltid kobler roten til det større treet under det mindre. Union by rank løser dette ved å spore den øvre grensen for trehøyden (rangen) og alltid koble det grunnere treet under det dypere.
Rangen er ikke nøyaktig lik høyden — path compression kan redusere høyden til under rangen — men den er en øvre grense. Ved å beholde det dypere treet som den nye roten sikrer vi at rangen bare øker når to trær med samme rang slås sammen, noe som begrenser den maksimale rangen til O(log n).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Attach lower-rank tree under higher-rank tree
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1 # only increases when ranks are equal
return TrueDe tre tilfellene ved union by rank
Når to komponenter med røttene px og py slås sammen, oppstår tre tilfeller basert på rangene deres:
- rank[px] > rank[py]: koble py under px — rangen til px er uendret
- rank[px] < rank[py]: koble px under py — rangen til py er uendret
- rank[px] == rank[py]: koble py under px (eller omvendt) — rangen til den nye roten øker med 1
Rangen økes bare i tilfellet med lik rang. Det betyr at rang n krever minst 2^n noder, slik at den maksimale rangen er O(log n). Dette holder find-stiene korte selv uten path compression.
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))Kombinert path compression og union by rank
Når både path compression og union by rank brukes sammen, synker den amortiserte tiden per operasjon til O(alpha(n)) — den inverse Ackermann-funksjonen. For enhver praktisk inndatastørrelse (opptil 2^65536) er alpha(n) høyst 4. Dette er i praksis konstant tid.
Path compression flater ut trær nedenfra og opp etter traverseringer, mens union by rank hindrer trærne i å bli høye ovenfra og ned under sammenslåinger. Sammen utfyller de hverandre: rang begrenser den opprinnelige dybden, og komprimering fjerner denne dybden etter den første traverseringen.
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very smallForstå den inverse Ackermann-funksjonen
Ackermann-funksjonen A(m, n) vokser ekstremt raskt — raskere enn enhver primitiv rekursiv funksjon. Den inverse funksjonen, alpha(n), defineres som den minste m slik at A(m, m) >= n. Fordi Ackermann-funksjonen vokser så raskt, vokser alpha(n) ufattelig langsomt.
For n = 10^80 (antallet atomer i det observerbare universet) er alpha(n) fortsatt bare 4. Derfor regnes DSU med begge optimaliseringene som konstant tid i praksis i alle praktiske sammenhenger. Man vil aldri møte et reelt problem som er stort nok til at alpha(n) overstiger 5.
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')Rang eller størrelse: Hva bør brukes?
Et alternativ til union by rank er union by size: det mindre treet kobles alltid under roten til det større treet. Begge tilnærmingene gir den samme garantien om en høyde på O(log n). Union by size er ofte enklere å forstå fordi størrelser er nøyaktige antall, mens ranger er øvre grenser som kanskje ikke gjenspeiler den faktiske høyden etter komprimering.
I intervjuer er begge tilnærmingene akseptable. Union by size har også fordelen at man får komponentstørrelser uten ekstra kostnad, noe mange problemer krever. Union by rank er litt mer elegant fra et teoretisk perspektiv og samsvarer med Tarjans opprinnelige bevis for den inverse Ackermann-grensen.
class DSUBySize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])Bevisskisse: Hvorfor rangen holder seg på O(log n)
Man kan bevise ved induksjon at et DSU-tre med rang r inneholder minst 2^r noder. Grunntilfelle: rang 0 betyr én node (2^0 = 1). Induksjonstrinn: rang r øker bare når to trær med rang r-1 slås sammen. Ifølge induksjonshypotesen har hvert deltre minst 2^(r-1) noder, så det sammenslåtte treet har minst 2 × 2^(r-1) = 2^r noder.
Siden et tre med rang r har minst 2^r noder, og vi har n noder totalt, er den maksimale rangen høyst log₂(n). Dette betyr at find uten path compression tar O(log n) tid, mens den amortiserte kostnaden med path compression synker betydelig mer.
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')DSU-mal for konkurranseprogrammering
I konkurranseprogrammering og intervjuer ønsker man en velprøvd DSU-mal som er kort, korrekt og håndterer alle kanttilfeller. Malen nedenfor bruker path halving (komprimering i én gjennomgang) kombinert med union by size — en kombinasjon som er enkel å skrive raskt og unngår rekursjon helt.
Initialiser alltid parent[i] = i og size[i] = 1. Husk at rotens size etter find gjenspeiler hele komponenten. Bruk aldri size[x] direkte — kall alltid size[find(x)].
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3Når DSU ikke er nok
DSU støtter sammenslåing av mengder, men støtter ikke oppsplitting av en mengde i to igjen. Hvis et problem krever både sammenslåing og oppsplitting av grupper, trenger man en annen datastruktur (for eksempel et link-cut-tre). DSU lagrer heller ikke elementene i hver gruppe direkte — det krever en ekstra naboskapliste eller ordbok.
Standard-DSU støtter dessuten ikke vektede kanter uten endringer (vektet DSU er en mer avansert variant). For problemer som å finne den billigste stien mellom sammenhengende noder er Dijkstra eller BFS mer passende. Ved å kjenne DSU-ens bruksområde unngår man å bruke den på feil måte.
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = pxSammenligning av DSU med BFS/DFS for sammenheng
Både BFS/DFS og DSU løser forespørsler om statisk sammenheng, men de har ulike styrker. BFS/DFS bruker O(V + E) og kan finne den faktiske stien mellom noder. DSU besvarer mange forespørsler om sammenheng over kantmengder som vokser trinnvis, med nær O(1) per forespørsel — ideelt for online-algoritmer der kanter kommer én om gangen.
Hvis alle kantene mottas på forhånd og det eneste som trengs, er å finne sammenheng, fungerer begge. Hvis kantene kommer dynamisk og det må besvares forespørsler om sammenheng etter hver nye kant, er DSU det klart beste valget. For problemer som også krever korteste vei, bør BFS brukes.
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')Øvelse: Minimumsspennende tre med DSU
Kruskal-algoritmen for minimumsspennende tre bruker DSU direkte. Sorter alle kantene etter vekt, og legg deretter grådig til hver kant hvis endepunktene ligger i ulike komponenter (ingen syklus). DSU utfører sykluskontrollen på nær O(1). Resultatet er et MST med n-1 kanter.
Dette er en klassisk demonstrasjon av styrken til DSU: Den forvandler en naiv sykluskontroll på O(E × V) til en prosess på O(E × alpha(n)). Med sortering i O(E log E) blir Kruskals totale kjøretid O(E log E), og DSU-operasjonene går så raskt at de er ubetydelige sammenlignet med sorteringen.
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)DSU med tilbakerulling: Offline-sammenheng
Standard-DSU støtter ikke angreoperasjoner. DSU med tilbakerulling (også kalt DSU med historikk) gjør derimot det: I stedet for path compression (som er vanskelig å angre), brukes bare union by rank, og hver union registreres i en stakk. Ved tilbakerulling tas elementer ut av stakken, og forelder og rang gjenopprettes. Dette gjør det mulig å løse offline-problemer med dynamisk sammenheng, der kanter kan legges til og fjernes.
Selv om dette er en avansert variant som sjelden dukker opp i vanlige intervjuer, viser den at union by rank er den avgjørende invarianten — ikke path compression. Uten path compression er hver find O(log n), og med tilbakerulling er stakkoperasjonene O(1), slik at den samlede kostnaden per operasjon blir O(log n) i stedet for O(alpha(n)).
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # FalseHurtigsjekk
Test forståelsen av begrepene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: union by rank fester alltid det grunnere treet under det dypere treet, rank øker bare når to trær med samme rang slås sammen, slik at trehøyden holdes på O(log n), og kombinasjonen av path compression og union by rank gir amortisert O(alpha(n)) — i praksis konstant tid. Deretter brukes den fullstendig optimale DSU-en til redundant forbindelse og syklusdeteksjon i grafer.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Union etter rang og den inverse Ackermann-grensen» gratis?
Ja – hele teksten i «Union etter rang og den inverse Ackermann-grensen» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Union etter rang og den inverse Ackermann-grensen»?
Legg til union basert på rang for å holde trærne flate, og forstå hvorfor de kombinerte optimaliseringene gir amortisert O(alpha(n))-tid – i praksis konstant tid. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Union etter rang og den inverse Ackermann-grensen»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- DSU med banekomprimering
- Union etter rang og den inverse Ackermann-grensen
- Redundant forbindelse og sykeloppdagelse
- Kontosammenslåing og sammenhengende komponenter