Union par rang et borne de l’inverse d’Ackermann
Ajoutez une union fondée sur le rang pour maintenir des arbres aplatis et comprenez pourquoi les optimisations combinées donnent un coût amorti en O(alpha(n)), donc pratiquement constant.
Union par rang et borne de l’inverse d’Ackermann est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Pourquoi les arbres deviennent hauts sans rang
La simple compression de chemin empêche les arbres de devenir hauts après les parcours, mais pendant les opérations union initiales, nous pouvons encore construire un arbre haut si nous attachons toujours la racine de l'arbre le plus grand sous celle du plus petit. L'union par rang résout ce problème en suivant la borne supérieure de la hauteur de l'arbre (le rang) et en attachant toujours l'arbre le moins profond sous le plus profond.
Le rang n'est pas exactement la hauteur : la compression de chemin peut réduire la hauteur en dessous du rang, mais il constitue une borne supérieure. En conservant l'arbre le plus profond comme nouvelle racine, nous garantissons que le rang n'augmente que lorsque deux arbres de même rang fusionnent, ce qui limite le rang maximal à 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 TrueLes trois cas de l'union par rang
Lors de la fusion de deux composantes dont les racines sont px et py, trois cas se présentent selon leurs rangs :
- rank[px] > rank[py] : attacher py sous px — rang de px inchangé
- rank[px] < rank[py] : attacher px sous py — rang de py inchangé
- rank[px] == rank[py] : attacher py sous px (ou l'inverse) — le rang de la nouvelle racine augmente de 1
Le rang n'augmente que dans le cas de rangs égaux. Cela signifie qu'un rang n nécessite au moins 2^n nœuds, de sorte que le rang maximal est O(log n). Les chemins de find restent ainsi courts, même sans compression de chemin.
# 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))Compression de chemin et union par rang combinées
Lorsque la compression de chemin et l'union par rang sont utilisées ensemble, le temps amorti par opération tombe à O(alpha(n)) — la fonction inverse d'Ackermann. Pour toute taille d'entrée pratique (jusqu'à 2^65536), alpha(n) est au plus égal à 4. Le temps d'exécution est donc effectivement constant.
La compression de chemin aplatit les arbres de bas en haut après les parcours, tandis que l'union par rang empêche les arbres de devenir hauts de haut en bas pendant les fusions. Elles sont donc complémentaires : le rang borne la profondeur initiale et la compression élimine cette profondeur après le premier parcours.
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 smallComprendre la fonction inverse d'Ackermann
La fonction d'Ackermann A(m, n) croît à une vitesse extraordinaire, plus rapidement que toute fonction récursive primitive. Son inverse, alpha(n), est défini comme le plus petit m tel que A(m, m) >= n. Comme la fonction d'Ackermann croît extrêmement rapidement, alpha(n) augmente à une lenteur inimaginable.
Pour n = 10^80 (le nombre d'atomes dans l'Univers observable), alpha(n) vaut toujours seulement 4. C'est pourquoi le DSU utilisant les deux optimisations est considéré comme ayant un temps effectivement constant dans toute situation pratique. Vous ne rencontrerez jamais de problème réel assez grand pour que alpha(n) dépasse 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 ou taille : que choisir ?
Une alternative à l'union par rang est l'union par taille : attachez toujours l'arbre de plus petite taille sous celui de plus grande taille. Les deux approches garantissent une hauteur en O(log n). L'union par taille est souvent plus facile à comprendre, car les tailles sont des comptes exacts, tandis que les rangs sont des bornes supérieures qui peuvent ne plus refléter la hauteur réelle après la compression.
Lors des entretiens, l'une ou l'autre approche est acceptable. L'union par taille permet en plus d'obtenir gratuitement la taille des composantes, ce qui est nécessaire dans de nombreux problèmes. L'union par rang est légèrement plus élégante sur le plan théorique et correspond à la preuve originale de Tarjan de la borne de l'inverse d'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)])Esquisse de preuve : pourquoi le rang reste en O(log n)
Nous pouvons démontrer par récurrence qu'un arbre de DSU de rang r contient au moins 2^r nœuds. Cas de base : le rang 0 correspond à un seul nœud (2^0 = 1). Étape d'induction : le rang r n'augmente que lorsque deux arbres de rang r-1 égal fusionnent. D'après l'hypothèse de récurrence, chaque sous-arbre contient au moins 2^(r-1) nœuds, donc l'arbre fusionné en contient au moins 2 × 2^(r-1) = 2^r.
Comme un arbre de rang r contient au moins 2^r nœuds et que nous avons n nœuds au total, le rang maximal est au plus log₂(n). Cela signifie que find sans compression de chemin prend un temps O(log n) et qu'avec la compression de chemin, le coût amorti diminue beaucoup davantage.
# 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}')Modèle de DSU pour la programmation compétitive
En programmation compétitive et lors des entretiens, vous voulez un modèle de DSU éprouvé, court, correct et capable de gérer tous les cas limites. Le modèle ci-dessous utilise la compression par moitié (compression en un seul passage) combinée à l'union par taille — une combinaison rapide à saisir et qui évite entièrement la récursion.
Initialisez toujours parent[i] = i et size[i] = 1. N'oubliez pas qu'après find, la size de la racine représente toute la composante. N'utilisez jamais size[x] directement : appelez toujours 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)) # 3Quand le DSU ne suffit pas
Le DSU permet de fusionner des ensembles, mais ne permet pas de séparer un ensemble en deux. Si un problème exige à la fois de regrouper et de séparer des groupes, vous avez besoin d'une autre structure (comme un arbre de liaison-coupe). Le DSU ne stocke pas non plus nativement les éléments de chaque groupe : vous avez besoin pour cela d'une liste d'adjacence ou d'un dictionnaire supplémentaire.
De plus, le DSU standard ne prend pas en charge les arêtes pondérées sans modification (le DSU pondéré est une variante plus avancée). Pour les problèmes comme celui du chemin le moins coûteux entre des nœuds connectés, Dijkstra ou BFS est plus approprié. Comprendre le domaine d'application du DSU évite de l'utiliser à tort.
# 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] = pxComparer DSU à BFS/DFS pour la connexité
BFS/DFS et DSU permettent tous deux de résoudre des requêtes de connexité statiques, mais ils ont des atouts différents. BFS/DFS s’exécute en O(V + E) et peut trouver le chemin réel entre les nœuds. DSU répond à de nombreuses requêtes de connexité sur des ensembles d’arêtes qui s’agrandissent progressivement, avec un coût proche de O(1) par requête — ce qui est idéal pour les algorithmes en ligne, où les arêtes arrivent une par une.
Si vous recevez toutes les arêtes à l’avance et que vous avez seulement besoin de la connexité, les deux approches conviennent. Si les arêtes arrivent dynamiquement et que vous devez répondre à des requêtes de connexité entre chaque nouvelle arête, DSU est clairement préférable. Pour les problèmes qui nécessitent également le plus court chemin, utilisez 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.')Exercice : arbre couvrant minimal avec DSU
L’algorithme de Kruskal pour construire un arbre couvrant minimal utilise directement DSU. Triez toutes les arêtes par poids, puis ajoutez chaque arête de manière gloutonne si ses extrémités appartiennent à des composantes différentes (donc sans former de cycle). DSU fournit cette vérification de cycle avec un coût proche de O(1). Le résultat est un MST de n-1 arêtes.
Il s’agit d’une démonstration classique de la puissance de DSU : il transforme une vérification naïve des cycles en O(E × V) en un processus en O(E × alpha(n)). Avec le tri en E log E, la durée totale de Kruskal est O(E log E), et les opérations de DSU sont si rapides qu’elles sont négligeables par rapport au tri.
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 avec rollback : connexité hors ligne
Le DSU standard ne prend pas en charge les opérations d’annulation. Cependant, DSU avec rollback (également appelé DSU avec historique) le permet : au lieu d’utiliser la compression de chemin (difficile à annuler), utilisez uniquement union par rang et enregistrez chaque union dans une pile. Pour revenir en arrière, retirez un élément avec pop de la pile et restaurez le parent et le rang. Cela permet de résoudre des problèmes de connexité dynamique hors ligne, dans lesquels des arêtes peuvent être ajoutées et supprimées.
Bien qu’il s’agisse d’une variante avancée rarement abordée dans les entretiens standard, elle montre que l’invariant essentiel est union par rang, et non la compression de chemin. Sans compression de chemin, chaque opération find coûte O(log n), et avec rollback, les opérations sur la pile coûtent O(1), ce qui donne O(log n) par opération au total au lieu de 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)) # FalseVérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que union par rang attache toujours l’arbre le moins profond sous l’arbre le plus profond, que le rang n’augmente que lorsque deux arbres de même rang fusionnent, ce qui maintient la hauteur de l’arbre à O(log n), et que la combinaison de la compression de chemin et de union par rang atteint O(alpha(n)) en coût amorti — soit, en pratique, un temps constant. Ensuite, nous appliquerons le DSU optimal à la connexion redondante et à la détection des cycles dans les graphes.
Questions Fréquemment Posées
La leçon « Union par rang et borne de l’inverse d’Ackermann » est-elle gratuite ?
Oui — le texte complet de « Union par rang et borne de l’inverse d’Ackermann » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Union par rang et borne de l’inverse d’Ackermann » ?
Ajoutez une union fondée sur le rang pour maintenir des arbres aplatis et comprenez pourquoi les optimisations combinées donnent un coût amorti en O(alpha(n)), donc pratiquement constant. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Union par rang et borne de l’inverse d’Ackermann » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- DSU avec compression de chemin
- Union par rang et borne de l’inverse d’Ackermann
- Connexion redondante et détection de cycles
- Fusion de comptes et composantes connexes