← Volver a los ejercicios

Qué pasa sin las heurísticas

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.

1. Antes de ver los dos bosques

Sin la unión por rango, el elemento más hondo queda a cuántos saltos de su raíz.

2. Las dos uniones

sin rango

def union(p, x, y):
    rx = raiz(p, x)
    ry = raiz(p, y)
    if rx != ry:
        p[ry] = rx

con rango

def 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] + 1

Las 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.

3. Operación por operación

En curso: Operación 0 de 7

sin rango

con rango

En rojo, el camino del elemento que más salta en cada bosque.

4. Lo que cuesta llegar a la raíz

5. Una sola llamada que acorta

Sobre los dos bosques del final, el find_set de la sesión, el que reescribe p al volver.

6. Para resolver

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.