Optimización del tamaño de Union-Find

Siguiendo la idea de la sección anterior, tomamos el conjunto de unión que se muestra en la siguiente figura y realizamosunion(4,9)la operación.

La estructura después de la operación de fusión es:

Se puede observar que el nivel de capas del árbol en esta estructura es relativamente alto; si en este momento aumenta la cantidad de elementos, el consumo generado será relativamente grande. Resolver este problema es en realidad muy simple: al realizar la operación de apuntado concreta, primero se juzga y se hace que el nodo raíz del conjunto con menos elementos apunte al nodo raíz del conjunto con más elementos, lo que con mayor probabilidad generará un árbol con menor profundidad.

Al construir el conjunto de unión se necesita un parámetro adicional,szel array,sz[i]que representa elinúmero de elementos en el conjunto con raíz en i.

// Constructor
public UnionFind3(int count){
    parent = new int[count];
    sz = new int[count];
    this.count = count;
    // Inicializar, cada parent[i] apunta a sí mismo, indicando que cada elemento forma un conjunto por sí mismo
    for( int i = 0 ; i < count ; i ++ ){
        parent[i] = i;
        sz[i] = 1;
    }
}

Al realizar la operación de fusión, se determina la dirección de la fusión según la diferencia en el número de elementos de los árboles donde se encuentran los dos elementos.

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    if( sz[pRoot] < sz[qRoot] ){
        parent[pRoot] = qRoot;
        sz[qRoot] += sz[pRoot];
    }
    else{
        parent[qRoot] = pRoot;
        sz[pRoot] += sz[qRoot];
    }
}

Después de la optimización, el resultado de la fusión es el siguiente: 9 apunta al nodo padre 8.

Código de ejemplo Java

Descarga del paquete fuente:Download

Código del archivo UnionFind3.java:

package ejemplo.union;

/**
* Optimización del tamaño de Union-Find
 */
public class UnionFind3 {
    // parent[i] representa el nodo padre al que apunta el elemento i
    private int[] parent;
    // sz[i] representa el número de elementos en el conjunto con raíz en i
    private int[] sz;
    // Cantidad de datos
    private int count;

    // Constructor
    public UnionFind3(int count){
        parent = new int[count];
        sz = new int[count];
        this.count = count;
        // Inicializar, cada parent[i] apunta a sí mismo, indicando que cada elemento forma un conjunto por sí mismo
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            sz[i] = 1;
        }
    }

    // Proceso de búsqueda, busca el número de conjunto correspondiente al elemento p
    // Complejidad O(h), donde h es la altura del árbol
    private int find(int p){
        assert( p >= 0 && p < count );
        // Consulta continuamente su nodo padre hasta llegar al nodo raíz
        // Característica del nodo raíz: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }

    // Comprueba si el elemento p y el elemento q pertenecen al mismo conjunto
    // Complejidad O(h), donde h es la altura del árbol
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // Fusiona el conjunto al que pertenecen el elemento p y el elemento q
    // Complejidad O(h), donde h es la altura del árbol
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        // Determina la dirección de la fusión según la diferencia en el número de elementos de los árboles donde se encuentran los dos elementos
        // Fusiona el conjunto con menos elementos en el conjunto con más elementos
        if( sz[pRoot] < sz[qRoot] ){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}
Otras extensiones