Union nach Rang und die inverse-Ackermann-Schranke
Ergänzen Sie Union nach Rang, um die Bäume flach zu halten, und verstehen Sie, warum die kombinierten Optimierungen amortisiert O(alpha(n)) ergeben – praktisch also konstante Zeit.
Union nach Rang und die inverse-Ackermann-Schranke ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum Bäume ohne Rang hoch werden
Reine Pfadkompression verhindert nach dem Durchlaufen hohe Bäume, aber während der anfänglichen Union-Operationen können wir weiterhin einen hohen Baum erzeugen, wenn wir die Wurzel des größeren Baums immer unter die des kleineren hängen. Union by Rank löst dieses Problem, indem es die obere Schranke der Baumhöhe (den Rang) verfolgt und den flacheren Baum immer unter den tieferen hängt.
Der Rang entspricht nicht exakt der Höhe – durch Pfadkompression kann die Höhe kleiner als der Rang werden –, ist aber eine obere Schranke. Indem wir den tieferen Baum als neue Wurzel beibehalten, stellen wir sicher, dass der Rang nur steigt, wenn zwei Bäume mit gleichem Rang zusammengeführt werden. Dadurch wird der maximale Rang auf O(log n) begrenzt.
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 TrueDie drei Fälle bei Union by Rank
Beim Zusammenführen zweier Komponenten mit den Wurzeln px und py ergeben sich abhängig von ihren Rängen drei Fälle:
- rank[px] > rank[py]: py unter px hängen – der Rang von px bleibt unverändert
- rank[px] < rank[py]: px unter py hängen – der Rang von py bleibt unverändert
- rank[px] == rank[py]: py unter px hängen (oder umgekehrt) – der Rang der neuen Wurzel steigt um 1
Der Rang wird nur im Fall gleicher Ränge erhöht. Das bedeutet, dass ein Rang von n mindestens 2^n Knoten erfordert. Daher beträgt der maximale Rang O(log n). Dadurch bleiben die find-Pfade auch ohne Pfadkompression kurz.
# 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))Kombinierte Pfadkompression und Union by Rank
Wenn Pfadkompression und Union by Rank gemeinsam verwendet werden, sinkt die amortisierte Laufzeit pro Operation auf O(alpha(n)) – die inverse Ackermann-Funktion. Für jede praktische Eingabegröße (bis zu 2^65536) ist alpha(n) höchstens 4. Damit ist die Laufzeit effektiv konstant.
Die Pfadkompression flacht Bäume nach dem Durchlaufen von unten nach oben ab, während Union by Rank verhindert, dass Bäume beim Zusammenführen von oben nach unten hoch werden. Zusammen ergänzen sie sich: Der Rang begrenzt die anfängliche Tiefe, und die Kompression beseitigt diese Tiefe nach dem ersten Durchlauf.
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 smallDie inverse Ackermann-Funktion verstehen
Die Ackermann-Funktion A(m, n) wächst außerordentlich schnell – schneller als jede primitiv-rekursive Funktion. Ihre Inverse, alpha(n), ist als kleinstes m definiert, für das A(m, m) >= n gilt. Da die Ackermann-Funktion so schnell wächst, wächst alpha(n) unvorstellbar langsam.
Für n = 10^80 (die Anzahl der Atome im beobachtbaren Universum) beträgt alpha(n) immer noch nur 4. Deshalb wird DSU mit beiden Optimierungen in jeder praktischen Umgebung als effektiv konstante Laufzeit betrachtet. Sie werden niemals auf ein reales Problem stoßen, das groß genug ist, damit alpha(n) 5 überschreitet.
# 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 oder Größe: Was ist die bessere Wahl
Eine Alternative zu Union by Rank ist Union by Size: Hängen Sie den Baum mit der kleineren Größe immer unter den Baum mit der größeren Größe. Beide Ansätze bieten dieselbe Garantie für eine Höhe von O(log n). Union by Size ist häufig leichter nachzuvollziehen, weil Größen exakte Anzahlen sind, während Ränge obere Schranken darstellen und nach der Kompression möglicherweise nicht mehr die tatsächliche Höhe widerspiegeln.
In Interviews sind beide Ansätze akzeptabel. Union by Size bietet zusätzlich Komponentengrößen ohne weiteren Aufwand, die bei vielen Problemen benötigt werden. Union by Rank ist theoretisch etwas eleganter und entspricht dem ursprünglichen Beweis von Tarjan für die Schranke der inversen Ackermann-Funktion.
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)])Beweisskizze: Warum der Rang bei O(log n) bleibt
Wir können durch Induktion beweisen, dass ein DSU-Baum mit Rang r mindestens 2^r Knoten enthält. Induktionsanfang: Rang 0 bedeutet einen einzelnen Knoten (2^0 = 1). Induktionsschritt: Der Rang r erhöht sich nur, wenn zwei Bäume mit gleichem Rang r-1 zusammengeführt werden. Nach der Induktionsannahme enthält jeder Teilbaum mindestens 2^(r-1) Knoten, sodass der zusammengeführte Baum mindestens 2 × 2^(r-1) = 2^r Knoten enthält.
Da ein Baum mit Rang r mindestens 2^r Knoten enthält und wir insgesamt n Knoten haben, beträgt der maximale Rang höchstens log₂(n). Das bedeutet, dass find ohne Pfadkompression O(log n) Zeit benötigt und die amortisierten Kosten mit Pfadkompression noch deutlich weiter sinken.
# 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-Vorlage für Competitive Programming
Beim Competitive Programming und in Interviews benötigen Sie eine praxiserprobte DSU-Vorlage, die kurz und korrekt ist und alle Randfälle behandelt. Die folgende Vorlage verwendet Pfadhalbierung (Kompression in einem Durchlauf) kombiniert mit Union by Size – eine Kombination, die sich schnell eintippen lässt und vollständig ohne Rekursion auskommt.
Initialisieren Sie immer parent[i] = i und size[i] = 1. Denken Sie daran, dass die size der Wurzel nach find die gesamte Komponente widerspiegelt. Verwenden Sie niemals size[x] direkt – rufen Sie immer size[find(x)] auf.
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)) # 3Wann DSU nicht ausreicht
DSU unterstützt das Zusammenführen von Mengen, aber nicht das Aufteilen einer Menge in zwei. Wenn ein Problem sowohl das Zusammenführen als auch das Trennen von Gruppen erfordert, benötigen Sie eine andere Datenstruktur (z. B. einen link-cut tree). DSU speichert außerdem nicht von selbst die Elemente jeder Gruppe – dafür benötigen Sie eine zusätzliche Adjazenzliste oder ein Dictionary.
Darüber hinaus unterstützt eine standardmäßige DSU gewichtete Kanten nicht ohne Anpassungen (Weighted DSU ist eine fortgeschrittenere Variante). Für Probleme wie den günstigsten Pfad zwischen verbundenen Knoten sind Dijkstra oder BFS besser geeignet. Wenn Sie den Anwendungsbereich von DSU kennen, vermeiden Sie eine falsche Anwendung.
# 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 im Vergleich zu BFS/DFS für Zusammenhang
Sowohl BFS/DFS als auch DSU lösen Abfragen zum statischen Zusammenhang, haben jedoch unterschiedliche Stärken. BFS/DFS läuft in O(V + E) und kann den tatsächlichen Pfad zwischen Knoten finden. DSU beantwortet viele Zusammenhangsabfragen über schrittweise wachsende Kantenmengen mit nahezu O(1) pro Abfrage – ideal für Online-Algorithmen, bei denen Kanten einzeln eintreffen.
Wenn Sie alle Kanten im Voraus erhalten und nur den Zusammenhang benötigen, sind beide Verfahren geeignet. Wenn Kanten dynamisch eintreffen und Sie nach jeder neuen Kante Zusammenhangsabfragen beantworten müssen, ist DSU eindeutig überlegen. Für Probleme, bei denen zusätzlich der kürzeste Pfad benötigt wird, sollten Sie BFS verwenden.
# 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.')Übung: Minimaler Spannbaum mit DSU
Der Kruskal-Algorithmus für den minimalen Spannbaum verwendet DSU direkt. Sortieren Sie alle Kanten nach Gewicht und fügen Sie dann jede Kante gierig hinzu, wenn ihre Endpunkte in verschiedenen Komponenten liegen (also keinen Zyklus bilden). DSU führt die Zyklusprüfung in nahezu O(1) aus. Das Ergebnis ist ein MST mit n-1 Kanten.
Dies ist ein klassisches Beispiel für die Leistungsfähigkeit von DSU: Eine naive Zyklusprüfung mit O(E × V) wird in einen Ablauf mit O(E × alpha(n)) umgewandelt. Zusammen mit der Sortierung in O(E log E) beträgt die Gesamtlaufzeit von Kruskal O(E log E), und die DSU-Operationen sind so schnell, dass sie gegenüber der Sortierung vernachlässigbar sind.
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 mit Rollback: Offline-Zusammenhang
Standard-DSU unterstützt keine Rückgängig-Operationen. DSU mit Rollback (auch DSU mit Verlauf genannt) unterstützt sie jedoch: Anstelle der Pfadkompression, die sich nur schwer rückgängig machen lässt, wird ausschließlich die Vereinigung nach Rang verwendet, und jede Vereinigung wird in einem Stapel protokolliert. Für ein Rollback wird der Stapel entfernt und parent sowie rank werden wiederhergestellt. Dadurch lassen sich Offline-Probleme zum dynamischen Zusammenhang lösen, bei denen Kanten hinzugefügt und entfernt werden können.
Diese fortgeschrittene Variante kommt zwar in gewöhnlichen Vorstellungsgesprächen selten vor, zeigt aber, dass die Vereinigung nach Rang die entscheidende Invariante ist – nicht die Pfadkompression. Ohne Pfadkompression benötigt jeder find O(log n), und mit Rollback dauern Stapeloperationen O(1). Damit ergibt sich insgesamt O(log n) pro Operation statt 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)) # FalseKurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die Vereinigung nach Rang hängt den flacheren Baum immer unter den tieferen Baum, der Rang wird nur erhöht, wenn zwei Bäume mit gleichem Rang zusammengeführt werden, wodurch die Baumhöhe bei O(log n) bleibt, und die Kombination aus Pfadkompression und Vereinigung nach Rang erreicht amortisiert O(alpha(n)) – also effektiv konstante Laufzeit. Als Nächstes wenden wir die vollständig optimierte DSU auf redundante Verbindungen und die Zykluserkennung in Graphen an.
Häufig gestellte Fragen
Ist die Lektion „Union nach Rang und die inverse-Ackermann-Schranke“ kostenlos?
Ja — der vollständige Text von „Union nach Rang und die inverse-Ackermann-Schranke“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Union nach Rang und die inverse-Ackermann-Schranke“?
Ergänzen Sie Union nach Rang, um die Bäume flach zu halten, und verstehen Sie, warum die kombinierten Optimierungen amortisiert O(alpha(n)) ergeben – praktisch also konstante Zeit. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Union nach Rang und die inverse-Ackermann-Schranke“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- DSU mit Pfadkompression
- Union nach Rang und die inverse-Ackermann-Schranke
- Redundante Verbindung und Zykluserkennung
- Accounts Merge und zusammenhängende Komponenten