Union by Rank en de inverse-Ackermann-grens
Voeg union op basis van rank toe om bomen vlak te houden en begrijp waarom de gecombineerde optimalisaties een geamortiseerde complexiteit van O(alpha(n)) opleveren — effectief constant.
Union by Rank en de inverse-Ackermann-grens is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Waarom bomen hoog worden zonder rang
Gewone padcompressie voorkomt hoge bomen na het doorlopen, maar tijdens de eerste samenvoegbewerkingen kunnen we nog steeds een hoge boom opbouwen als we de wortel van de grotere boom altijd onder de kleinere hangen. Samenvoegen op rang lost dit op door de bovengrens van de boomhoogte (de rang) bij te houden en de ondiepere boom altijd onder de diepere te hangen.
De rang is niet precies de hoogte: door padcompressie kan de hoogte kleiner worden dan de rang, maar de rang blijft wel een bovengrens. Door de diepere boom de nieuwe wortel te laten blijven, zorgen we ervoor dat de rang alleen toeneemt wanneer twee bomen met dezelfde rang worden samengevoegd. Daardoor blijft de maximale rang 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 drie gevallen van samenvoegen op rang
Bij het samenvoegen van twee componenten met de wortels px en py ontstaan op basis van hun rangen drie gevallen:
- rank[px] > rank[py]: hang py onder px — de rang van px blijft onveranderd
- rank[px] < rank[py]: hang px onder py — de rang van py blijft onveranderd
- rank[px] == rank[py]: hang py onder px (of andersom) — de rang van de nieuwe wortel neemt met 1 toe
De rang wordt alleen verhoogd in het geval van gelijke rangen. Dit betekent dat rang n minstens 2^n knooppunten vereist, waardoor de maximale rang O(log n) is. Hierdoor blijven find-paden kort, zelfs zonder padcompressie.
# 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))Gecombineerde padcompressie en samenvoegen op rang
Wanneer padcompressie en samenvoegen op rang samen worden gebruikt, daalt de geamortiseerde tijd per bewerking naar O(alpha(n)): de inverse Ackermannfunctie. Voor elke praktische invoergrootte (tot 2^65536) is alpha(n) hooguit 4. Dit is in feite constante tijd.
Padcompressie maakt bomen van onderaf platter na het doorlopen, terwijl samenvoegen op rang voorkomt dat bomen tijdens samenvoegingen van bovenaf hoog worden. Samen vullen ze elkaar aan: rang begrenst de aanvankelijke diepte en compressie elimineert die diepte na de eerste doorloop.
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 smallDe inverse Ackermannfunctie begrijpen
De Ackermannfunctie A(m, n) groeit buitengewoon snel, sneller dan elke primitief recursieve functie. De inverse functie, alpha(n), is gedefinieerd als de kleinste m waarvoor A(m, m) >= n. Omdat de Ackermannfunctie zo snel groeit, neemt alpha(n) onvoorstelbaar langzaam toe.
Voor n = 10^80 (het aantal atomen in het waarneembare heelal) is alpha(n) nog steeds slechts 4. Daarom wordt DSU met beide optimalisaties in elke praktische situatie beschouwd als een algoritme met effectief constante tijd. Je zult nooit een echt probleem tegenkomen dat groot genoeg is om alpha(n) groter dan 5 te maken.
# 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 versus grootte: welke kies je?
Een alternatief voor samenvoegen op rang is samenvoegen op grootte: hang de boom met de kleinere grootte altijd onder de wortel van de boom met de grotere grootte. Beide aanpakken geven dezelfde garantie van een hoogte van O(log n). Samenvoegen op grootte is vaak eenvoudiger te begrijpen, omdat groottes exacte aantallen zijn, terwijl rangen bovengrenzen zijn die na compressie mogelijk niet de werkelijke hoogte weerspiegelen.
Bij interviews zijn beide aanpakken acceptabel. Samenvoegen op grootte heeft als extra voordeel dat je de componentgroottes zonder extra kosten krijgt, wat veel problemen vereisen. Samenvoegen op rang is theoretisch iets eleganter en sluit aan bij het oorspronkelijke bewijs van Tarjan voor de grens van de inverse Ackermannfunctie.
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)])Bewijsschets: waarom de rang O(log n) blijft
We kunnen met inductie bewijzen dat een DSU-boom met rang r minstens 2^r knooppunten bevat. Basisgeval: rang 0 betekent één knooppunt (2^0 = 1). Inductiestap: rang r neemt alleen toe wanneer twee bomen met dezelfde rang r-1 worden samengevoegd. Volgens de inductiehypothese heeft elke deelboom minstens 2^(r-1) knooppunten, dus bevat de samengevoegde boom minstens 2 × 2^(r-1) = 2^r knooppunten.
Omdat een boom met rang r minstens 2^r knooppunten heeft en we in totaal n knooppunten hebben, is de maximale rang hooguit log₂(n). Dit betekent dat find zonder padcompressie O(log n) tijd kost, en dat de geamortiseerde kosten met padcompressie nog veel verder dalen.
# 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-sjabloon voor competitief programmeren
Bij competitief programmeren en interviews wil je een beproefd DSU-sjabloon dat kort en correct is en alle randgevallen afhandelt. Het onderstaande sjabloon gebruikt padhalvering (compressie in één doorgang) in combinatie met samenvoegen op grootte. Deze combinatie is snel te typen en vermijdt recursie volledig.
Initialiseer altijd parent[i] = i en size[i] = 1. Onthoud dat na find de waarde van size bij de wortel de hele component weerspiegelt. Gebruik nooit rechtstreeks size[x]; roep altijd size[find(x)] aan.
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)) # 3Wanneer DSU niet volstaat
DSU ondersteunt het samenvoegen van verzamelingen, maar niet het opsplitsen van een verzameling in twee delen. Als een probleem zowel het samenvoegen als het scheiden van groepen vereist, heb je een andere gegevensstructuur nodig, zoals een link-cut-boom. DSU slaat de elementen van elke groep ook niet standaard op; daarvoor heb je een extra adjacentielijst of woordenboek nodig.
Daarnaast ondersteunt een standaard-DSU gewogen kanten niet zonder aanpassingen (een gewogen DSU is een geavanceerdere variant). Voor problemen zoals het vinden van het goedkoopste pad tussen verbonden knooppunten zijn Dijkstra of BFS geschikter. Als je het toepassingsgebied van DSU herkent, voorkom je dat je de structuur verkeerd toepast.
# 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] = pxDSU en BFS/DFS vergelijken voor connectiviteit
Zowel BFS/DFS als DSU lossen statische connectiviteitsvragen op, maar ze hebben verschillende sterke punten. BFS/DFS werkt in O(V + E) en kan het daadwerkelijke pad tussen knopen vinden. DSU beantwoordt veel connectiviteitsvragen over stapsgewijs groeiende verzamelingen verbindingen in bijna-O(1) per vraag — ideaal voor onlinealgoritmen waarbij verbindingen één voor één binnenkomen.
Als je alle verbindingen vooraf ontvangt en alleen connectiviteit nodig hebt, werkt een van beide. Als verbindingen dynamisch binnenkomen en je na elke nieuwe verbinding connectiviteitsvragen moet beantwoorden, is DSU duidelijk de beste keuze. Voor problemen waarbij je ook het kortste pad nodig hebt, blijf je bij BFS.
# 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.')Oefening: minimale opspannende boom met DSU
Het algoritme van Kruskal voor een minimale opspannende boom gebruikt DSU rechtstreeks. Sorteer alle verbindingen op gewicht en voeg vervolgens hebzuchtig elke verbinding toe als de eindpunten in verschillende componenten zitten (geen cyclus). DSU levert de cycluscontrole in bijna-O(1). Het resultaat is een MST met n-1 verbindingen.
Dit is een klassiek voorbeeld van de kracht van DSU: het zet een naïeve cycluscontrole van O(E × V) om in een proces van O(E × alpha(n)). Met het sorteren in E log E-tijd is de totale tijd van Kruskal O(E log E), en DSU-bewerkingen zijn zo snel dat ze verwaarloosbaar zijn vergeleken met het sorteren.
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 met terugdraaien: offline connectiviteit
Standaard-DSU ondersteunt geen bewerkingen om ongedaan te maken. DSU met terugdraaien (ook DSU met geschiedenis genoemd) doet dat wel: gebruik in plaats van padcompressie (die moeilijk ongedaan te maken is) alleen verenigen op rang en leg elke vereniging vast in een stapel. Als je wilt terugdraaien, haal je items van de stapel en herstel je ouder en rang. Hiermee kun je offlineproblemen met dynamische connectiviteit oplossen waarin verbindingen kunnen worden toegevoegd en verwijderd.
Hoewel dit een geavanceerde variant is die je zelden in standaard technische sollicitatiegesprekken ziet, laat hij zien dat verenigen op rang de cruciale invariant is — niet padcompressie. Zonder padcompressie kost elke find-bewerking O(log n), en met terugdraaien kosten stapelbewerkingen O(1). Daardoor kost elke bewerking in totaal O(log n) in plaats van 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)) # FalseKorte controle
Controleer je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: verenigen op rang koppelt de ondiepere boom altijd onder de diepere boom, de rang wordt alleen verhoogd wanneer twee bomen met dezelfde rang worden samengevoegd, waardoor de boomhoogte O(log n) blijft, en door padcompressie te combineren met verenigen op rang bereik je geamortiseerd O(alpha(n)) — praktisch constante tijd. Hierna passen we de volledig optimale DSU toe op overtollige verbindingen en cyclusdetectie in grafen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Union by Rank en de inverse-Ackermann-grens” gratis?
Ja — de volledige tekst van “Union by Rank en de inverse-Ackermann-grens” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Union by Rank en de inverse-Ackermann-grens”?
Voeg union op basis van rank toe om bomen vlak te houden en begrijp waarom de gecombineerde optimalisaties een geamortiseerde complexiteit van O(alpha(n)) opleveren — effectief constant. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Union by Rank en de inverse-Ackermann-grens”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- DSU met padcompressie
- Union by Rank en de inverse-Ackermann-grens
- Redundant Connection en cyclusdetectie
- Accounts Merge en verbonden componenten