Union per rango e limite dell'inversa di Ackermann
Aggiunga l'unione basata sul rango per mantenere piatti gli alberi e comprenda perché le ottimizzazioni combinate garantiscano un costo ammortizzato O(alpha(n)), di fatto costante.
Union per rango e limite dell'inversa di Ackermann è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Perché gli alberi diventano alti senza il rango
La semplice compressione dei cammini impedisce agli alberi di rimanere alti dopo gli attraversamenti, ma durante le operazioni union iniziali è comunque possibile costruire un albero alto se si collega sempre la radice dell'albero più grande sotto quella dell'albero più piccolo. L'unione per rango risolve il problema tenendo traccia del limite superiore dell'altezza dell'albero (il rango) e collegando sempre l'albero meno profondo sotto quello più profondo.
Il rango non corrisponde esattamente all'altezza: la compressione dei cammini può ridurre l'altezza al di sotto del rango, ma il rango rimane un limite superiore. Mantenendo come nuova radice l'albero più profondo, si fa in modo che il rango aumenti soltanto quando si fondono due alberi con lo stesso rango, limitando il rango massimo a 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 TrueI tre casi dell'unione per rango
Quando si fondono due componenti con radici px e py, si presentano tre casi in base ai rispettivi ranghi:
- rank[px] > rank[py]: si collega py sotto px; il rango di px rimane invariato
- rank[px] < rank[py]: si collega px sotto py; il rango di py rimane invariato
- rank[px] == rank[py]: si collega py sotto px (o viceversa); il rango della nuova radice aumenta di 1
Il rango aumenta solo nel caso di ranghi uguali. Ciò significa che un rango n richiede almeno 2^n nodi, quindi il rango massimo è O(log n). In questo modo i cammini di find rimangono brevi anche senza la compressione dei cammini.
# 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))Compressione dei cammini e unione per rango combinate
Quando si usano insieme la compressione dei cammini e l'unione per rango, il tempo ammortizzato per operazione scende a O(alpha(n)), dove alpha(n) è la funzione inversa di Ackermann. Per qualsiasi dimensione pratica dell'input (fino a 2^65536), alpha(n) è al massimo 4. Si tratta, di fatto, di un tempo costante.
La compressione dei cammini appiattisce gli alberi dal basso verso l'alto dopo gli attraversamenti, mentre l'unione per rango impedisce agli alberi di diventare alti dall'alto verso il basso durante le fusioni. Insieme sono complementari: il rango limita la profondità iniziale e la compressione elimina tale profondità dopo il primo attraversamento.
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 smallComprendere la funzione inversa di Ackermann
La funzione di Ackermann A(m, n) cresce a una velocità straordinaria, più rapidamente di qualsiasi funzione ricorsiva primitiva. La sua inversa, alpha(n), è definita come il più piccolo valore m tale che A(m, m) >= n. Poiché la funzione di Ackermann cresce così rapidamente, alpha(n) cresce in modo incredibilmente lento.
Per n = 10^80 (il numero di atomi nell'universo osservabile), alpha(n) è ancora soltanto 4. Per questo motivo, la DSU con entrambe le ottimizzazioni viene considerata con tempo effettivamente costante in ogni contesto pratico. Non si incontrerà mai un problema reale abbastanza grande da far superare ad alpha(n) il valore 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.')Rango o dimensione: quale usare?
Un'alternativa all'unione per rango è l'unione per dimensione: si collega sempre l'albero di dimensione minore sotto quello di dimensione maggiore. Entrambi gli approcci garantiscono la stessa altezza O(log n). L'unione per dimensione è spesso più intuitiva, perché le dimensioni sono conteggi esatti, mentre i ranghi sono limiti superiori che, dopo la compressione, potrebbero non riflettere l'altezza effettiva.
Nei colloqui tecnici, entrambi gli approcci sono accettabili. L'unione per dimensione offre inoltre gratuitamente le dimensioni delle componenti, necessarie in molti problemi. L'unione per rango è leggermente più elegante dal punto di vista teorico e corrisponde alla dimostrazione originale di Tarjan del limite dato dalla funzione inversa di Ackermann.
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)])Schema della dimostrazione: perché il rango rimane O(log n)
Si può dimostrare per induzione che un albero DSU di rango r contiene almeno 2^r nodi. Caso base: il rango 0 corrisponde a un singolo nodo (2^0 = 1). Passo induttivo: il rango r aumenta soltanto quando si fondono due alberi di rango r-1 uguale. Per ipotesi induttiva, ogni sottoalbero contiene almeno 2^(r-1) nodi, quindi l'albero risultante contiene almeno 2 × 2^(r-1) = 2^r nodi.
Poiché un albero di rango r contiene almeno 2^r nodi e i nodi totali sono n, il rango massimo è al più log₂(n). Di conseguenza, find senza compressione dei cammini richiede O(log n) tempo, mentre con la compressione dei cammini il costo ammortizzato diminuisce ulteriormente.
# 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}')Template DSU per la programmazione competitiva
Nella programmazione competitiva e nei colloqui tecnici, è utile disporre di un template DSU collaudato, breve, corretto e capace di gestire tutti i casi limite. Il template seguente usa il dimezzamento dei cammini (compressione in un solo passaggio) combinato con l'unione per dimensione: una combinazione facile da digitare rapidamente e che evita completamente la ricorsione.
Si inizializzino sempre parent[i] = i e size[i] = 1. Si ricordi che, dopo find, il valore di size della radice rappresenta l'intera componente. Non si usi mai direttamente size[x]: si chiami sempre 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)) # 3Quando la DSU non è sufficiente
La DSU supporta la fusione degli insiemi, ma non supporta la divisione di un insieme in due. Se un problema richiede sia di unire sia di separare i gruppi, è necessaria una struttura diversa (come un link-cut tree). Inoltre, la DSU non memorizza nativamente gli elementi di ogni gruppo: per farlo serve una lista di adiacenza o un dizionario aggiuntivo.
Inoltre, la DSU standard non supporta gli archi pesati senza modifiche (la DSU pesata è una variante più avanzata). Per problemi come trovare il cammino meno costoso tra nodi connessi, è più appropriato usare Dijkstra o BFS. Riconoscere l'ambito di applicazione della DSU evita di usarla in modo improprio.
# 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] = pxConfronto tra DSU e BFS/DFS per la connettività
Sia BFS/DFS sia DSU risolvono query di connettività statiche, ma hanno punti di forza diversi. BFS/DFS ha complessità O(V + E) e può trovare il percorso effettivo tra i nodi. DSU risponde a molte query di connettività su insiemi di archi che crescono progressivamente con un costo quasi O(1) per query: è l'ideale per algoritmi online in cui gli archi arrivano uno alla volta.
Se si ricevono tutti gli archi in anticipo e serve solo la connettività, entrambe le soluzioni sono valide. Se gli archi arrivano dinamicamente e occorre rispondere a query di connettività dopo ogni nuovo arco, DSU è nettamente superiore. Per i problemi che richiedono anche il percorso più breve, conviene usare 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.')Esercizio: albero ricoprente minimo con DSU
L'algoritmo di Kruskal per l'albero ricoprente minimo usa direttamente DSU. Si ordinano tutti gli archi in base al peso, poi si aggiunge greedy ciascun arco se i suoi estremi appartengono a componenti diverse (quindi non si crea un ciclo). DSU fornisce il controllo dei cicli in un tempo quasi O(1). Il risultato è un MST con n-1 archi.
Questa è una dimostrazione classica della potenza di DSU: trasforma un controllo ingenuo dei cicli di O(E × V) in un processo di O(E × alpha(n)). Con l'ordinamento E log E, il tempo totale di Kruskal è O(E log E), mentre le operazioni di DSU sono così rapide da risultare trascurabili rispetto all'ordinamento.
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 con rollback: connettività offline
La DSU standard non supporta operazioni di annullamento. Tuttavia, la DSU con rollback (detta anche DSU con cronologia) le supporta: invece della compressione dei cammini (difficile da annullare), si utilizza solo l'unione per rango e si registra ogni unione in uno stack. Per eseguire il rollback, si estrae un elemento dallo stack e si ripristinano parent e rank. Questo permette di risolvere problemi di connettività dinamica offline in cui gli archi possono essere aggiunti e rimossi.
Sebbene sia una variante avanzata, raramente presente nei colloqui standard, dimostra che l'invariante fondamentale è l'unione per rango, non la compressione dei cammini. Senza compressione dei cammini, ogni find ha complessità O(log n) e, con il rollback, le operazioni sullo stack sono O(1): si ottiene quindi O(log n) per operazione complessiva invece di 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)) # FalseVerifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: l'unione per rango collega sempre l'albero meno profondo sotto quello più profondo, rank aumenta solo quando si uniscono due alberi dello stesso rango, mantenendo l'altezza dell'albero a O(log n) e la combinazione della compressione dei cammini con l'unione per rango raggiunge O(alpha(n)) ammortizzato, cioè un tempo effettivamente costante. Nella prossima lezione applicheremo la DSU ottimale al problema Redundant Connection e al rilevamento dei cicli nei grafi.
Domande Frequenti
La lezione «Union per rango e limite dell'inversa di Ackermann» è gratuita?
Sì — il testo completo di «Union per rango e limite dell'inversa di Ackermann» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Union per rango e limite dell'inversa di Ackermann»?
Aggiunga l'unione basata sul rango per mantenere piatti gli alberi e comprenda perché le ottimizzazioni combinate garantiscano un costo ammortizzato O(alpha(n)), di fatto costante. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Union per rango e limite dell'inversa di Ackermann»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- DSU con compressione dei cammini
- Union per rango e limite dell'inversa di Ackermann
- Connessione ridondante e rilevamento dei cicli
- Unione di account e componenti connesse