Union-find y conjuntos disjuntos

Un árbol para AGRUPAR, no para buscar. Fusiona grupos + prueba "¿mismo grupo?" en tiempo ≈ constante.

Conjuntos como árboles nombrados por su raíz

• Cada elemento apunta a un padre; raíz = el nombre del grupo
• Mismo grupo ⟺ misma raíz
• Union por rango: cuelga el árbol más bajo debajo del más alto
• Compresión de caminos: en cada find, apunta todo directo a la raíz

Mira las fusiones + la compresión de caminos

Fusiona pares → cuartetos → uno solo. Luego find(7) comprime el camino a la raíz. La estructura se aplana sola conforme la usas.

O(α(n)) — casi constante

α(n) ≤ 4 para cualquier n real. 566× más rápido que el union ingenuo O(n) con n=16000.

Solo fusiona, nunca separa

• No hay un "des-union" eficiente (la compresión revolvió el árbol)
• Responde una sola pregunta — "¿mismo grupo?" — tan rápido como es posible
• Ambas optimizaciones se necesitan juntas para la cota α(n)

Para llevar

Unas cuantas líneas le ganan a un speedup de hardware de 566× — las ganancias son algorítmicas. Mueve a Kruskal, componentes conexas, detección de ciclos. Siguiente bloque: grafos.