Las mismas siete uniones corren dos veces, con un find_set que sube hasta
la raíz sin acortar el camino. A la izquierda, colgando siempre la segunda raíz de la primera; a la
derecha, comparando los rangos.
Sin la unión por rango, el elemento más hondo queda a cuántos saltos de su raíz.
def union(p, x, y):
rx = raiz(p, x)
ry = raiz(p, y)
if rx != ry:
p[ry] = rxdef union(p, rango, x, y):
rx = raiz(p, x)
ry = raiz(p, y)
if rx != ry:
if rango[rx] < rango[ry]:
p[rx] = ry
elif rango[rx] > rango[ry]:
p[ry] = rx
else:
p[ry] = rx
rango[rx] = rango[rx] + 1Las dos llaman a raiz, que sube sin tocar p, de modo que la
única diferencia entre las dos columnas son las tres ramas del if interno.
Sobre los dos bosques del final, el find_set de
la sesión, el que reescribe p al volver.
Escriba una secuencia de uniones sobre ocho elementos que deje un árbol de altura 3 con la unión por rango encendida. Después diga si existe una que llegue a altura 4.