Unión por rango y cota de Ackermann inversa
Añada la unión basada en rangos para mantener los árboles planos y comprenda por qué las optimizaciones combinadas producen un coste amortizado de O(alpha(n)), prácticamente constante.
Unión por rango y cota de Ackermann inversa es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Por qué los árboles crecen sin rank
La compresión de caminos por sí sola evita los árboles altos después de recorrerlos, pero durante las operaciones union iniciales aún podemos construir un árbol alto si siempre adjuntamos la raíz del árbol más grande bajo la del más pequeño. Union by rank resuelve esto realizando un seguimiento de la cota superior de la altura del árbol (el rank) y adjuntando siempre el árbol menos profundo bajo el más profundo.
El rank no es exactamente la altura: la compresión de caminos puede reducir la altura por debajo del rank, pero sí es una cota superior. Al conservar como nueva raíz el árbol más profundo, garantizamos que el rank solo aumente cuando se fusionan dos árboles con el mismo rank, lo que limita el rank máximo 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 TrueLos tres casos de union by rank
Al fusionar dos componentes con raíces px y py, se presentan tres casos según sus ranks:
- rank[px] > rank[py]: adjuntar py bajo px; el rank de px no cambia
- rank[px] < rank[py]: adjuntar px bajo py; el rank de py no cambia
- rank[px] == rank[py]: adjuntar py bajo px (o al revés); el rank de la nueva raíz aumenta en 1
El rank solo se incrementa en el caso de ranks iguales. Esto significa que un rank n requiere al menos 2^n nodos, por lo que el rank máximo es O(log n). Así, los caminos de find son cortos incluso sin compresión de caminos.
# 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))Compresión de caminos y union by rank combinadas
Cuando se utilizan juntas la compresión de caminos y union by rank, el tiempo amortizado por operación se reduce a O(alpha(n)), la función de Ackermann inversa. Para cualquier tamaño de entrada práctico (hasta 2^65536), alpha(n) es como máximo 4. En la práctica, esto equivale a tiempo constante.
La compresión de caminos aplana los árboles de abajo arriba después de recorrerlos, mientras que union by rank evita que los árboles crezcan demasiado desde arriba durante las fusiones. Juntas son complementarias: rank limita la profundidad inicial y la compresión elimina esa profundidad después del primer recorrido.
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 smallComprender la función de Ackermann inversa
La función de Ackermann A(m, n) crece extraordinariamente rápido, más rápido que cualquier función recursiva primitiva. Su inversa, alpha(n), se define como el menor m tal que A(m, m) >= n. Como la función de Ackermann crece tan rápidamente, alpha(n) crece de forma inimaginablemente lenta.
Para n = 10^80 (el número de átomos del universo observable), alpha(n) sigue siendo solo 4. Por eso el DSU con ambas optimizaciones se considera de tiempo efectivamente constante en cualquier situación práctica. Nunca se encontrará con un problema real lo bastante grande como para que alpha(n) supere 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.')Rank frente a size: ¿cuál utilizar?
Una alternativa a union by rank es union by size: siempre se adjunta el árbol de menor tamaño bajo el árbol de mayor tamaño. Ambos enfoques proporcionan la misma garantía de altura O(log n). Union by size suele ser más fácil de razonar porque los tamaños son conteos exactos, mientras que los ranks son cotas superiores que quizá no reflejen la altura real después de la compresión.
En las entrevistas, cualquiera de los dos enfoques es válido. Union by size ofrece además los tamaños de las componentes sin coste adicional, algo que muchos problemas requieren. Union by rank es ligeramente más elegante desde el punto de vista teórico y coincide con la demostración original de Tarjan de la cota de Ackermann inversa.
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)])Esbozo de demostración: por qué rank se mantiene en O(log n)
Podemos demostrar por inducción que un árbol DSU con rank r contiene al menos 2^r nodos. Caso base: rank 0 significa un único nodo (2^0 = 1). Paso inductivo: el rank r solo aumenta cuando se fusionan dos árboles de rank r-1 iguales. Según la hipótesis inductiva, cada subárbol tiene al menos 2^(r-1) nodos, por lo que el árbol fusionado tiene al menos 2 × 2^(r-1) = 2^r nodos.
Como un árbol de rank r tiene al menos 2^r nodos y disponemos de n nodos en total, el rank máximo es como mucho log₂(n). Esto significa que find sin compresión de caminos tarda O(log n), mientras que con compresión de caminos el coste amortizado se reduce mucho más.
# 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}')Plantilla DSU para programación competitiva
En programación competitiva y en entrevistas, necesita una plantilla DSU probada, breve, correcta y capaz de gestionar todos los casos límite. La plantilla siguiente utiliza reducción a la mitad del camino (compresión en una pasada) combinada con union by size, una combinación fácil de escribir rápidamente y que evita por completo la recursión.
Inicialice siempre parent[i] = i y size[i] = 1. Recuerde que, después de find, el size de la raíz refleja toda la componente. Nunca utilice size[x] directamente; llame siempre a 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)) # 3Cuándo DSU no es suficiente
DSU permite fusionar conjuntos, pero no permite separar un conjunto de nuevo en dos. Si un problema requiere unir y separar grupos, necesita otra estructura (como un árbol link-cut). Además, DSU no almacena de forma nativa los elementos de cada grupo; para ello necesita una lista de adyacencia o un diccionario adicional.
Asimismo, el DSU estándar no admite aristas ponderadas sin modificaciones (el DSU ponderado es una variante más avanzada). Para problemas como encontrar el camino más barato entre nodos conectados, Dijkstra o BFS son más apropiados. Reconocer el alcance del DSU evita aplicarlo de forma incorrecta.
# 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] = pxComparación de DSU con BFS/DFS para la conectividad
Tanto BFS/DFS como DSU resuelven consultas de conectividad estática, pero tienen distintas ventajas. BFS/DFS se ejecuta en O(V + E) y puede encontrar el camino real entre nodos. DSU responde a muchas consultas de conectividad sobre conjuntos de aristas que crecen progresivamente, con un coste cercano a O(1) por consulta; es ideal para algoritmos en línea, en los que las aristas llegan una a una.
Si recibe todas las aristas por adelantado y solo necesita consultar la conectividad, cualquiera de los dos métodos funciona. Si las aristas llegan dinámicamente y necesita responder consultas de conectividad después de cada nueva arista, DSU es claramente superior. Para problemas que también requieren el camino más corto, utilice 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.')Práctica: árbol de expansión mínima con DSU
El algoritmo de Kruskal para obtener un árbol de expansión mínima utiliza DSU directamente. Ordene todas las aristas por peso y, a continuación, añada de forma voraz cada arista cuyos extremos estén en componentes diferentes (es decir, que no forme un ciclo). DSU proporciona la comprobación de ciclos en un tiempo cercano a O(1). El resultado es un MST de n-1 aristas.
Esta es una demostración clásica de la potencia de DSU: convierte una comprobación ingenua de ciclos de O(E × V) en un proceso de O(E × alpha(n)). Con la ordenación de coste E log E, el tiempo total de Kruskal es O(E log E), y las operaciones de DSU son tan rápidas que resultan insignificantes frente a la ordenación.
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 reversión: conectividad fuera de línea
El DSU estándar no admite operaciones de deshacer. Sin embargo, DSU con reversión (también llamado DSU con historial) sí las admite: en lugar de utilizar compresión de caminos (que es difícil de deshacer), utilice únicamente unión por rango y registre cada unión en una pila. Para revertir una operación, extraiga un elemento de la pila y restaure el padre y el rango. Esto permite resolver problemas de conectividad dinámica fuera de línea en los que las aristas pueden añadirse y eliminarse.
Aunque esta es una variante avanzada que rara vez aparece en entrevistas estándar, demuestra que la unión por rango es la invariante fundamental, no la compresión de caminos. Sin compresión de caminos, cada búsqueda cuesta O(log n), y con la reversión las operaciones de la pila cuestan O(1), por lo que el coste total por operación es O(log n) en lugar 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)) # FalseComprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: la unión por rango siempre coloca el árbol de menor altura debajo del árbol de mayor altura, el rango solo aumenta cuando se fusionan dos árboles del mismo rango, lo que mantiene la altura del árbol en O(log n), y combinar la compresión de caminos con la unión por rango consigue un coste amortizado de O(alpha(n)), es decir, un tiempo efectivamente constante. A continuación, aplicaremos el DSU completamente optimizado a la conexión redundante y la detección de ciclos en grafos.
Preguntas frecuentes
¿La lección «Unión por rango y cota de Ackermann inversa» es gratis?
Sí — el texto completo de «Unión por rango y cota de Ackermann inversa» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Unión por rango y cota de Ackermann inversa»?
Añada la unión basada en rangos para mantener los árboles planos y comprenda por qué las optimizaciones combinadas producen un coste amortizado de O(alpha(n)), prácticamente constante. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Unión por rango y cota de Ackermann inversa»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- DSU con compresión de caminos
- Unión por rango y cota de Ackermann inversa
- Conexión redundante y detección de ciclos
- Fusión de cuentas y componentes conexas