Compresión de ruta de Union-Find

La función find en Union-Find puede realizar compresión de ruta para encontrar más rápidamente el nodo raíz de un punto. Para un árbol de conjuntos, debajo de su nodo raíz pueden haber muchos nodos adjuntos. Por lo tanto, podemos intentar, durante el proceso de find, ir de abajo hacia arriba; si el nodo visitado no es el nodo raíz, entonces podemos mover ese nodo hacia arriba tanto como sea posible, reduciendo el número de niveles del árbol. Este proceso se llama compresión de ruta.

Como se muestra en la siguiente figura, el proceso de find(4) puede usar compresión de ruta para reducir el número de niveles del árbol.

Cuando el nodo 4 busca hacia arriba el nodo raíz, en el primer paso de la compresión, el número de niveles del árbol se reduce en uno:

El nodo 2 busca hacia arriba y tampoco es el nodo raíz, entonces se hace que el elemento 2 apunte al padre del padre original. Después de la operación, el número de niveles del árbol se reduce en uno correspondientemente, y se devuelve el nodo raíz 0.

El código del proceso find se modifica a:

// Proceso de búsqueda, encuentra el número de conjunto correspondiente al elemento p
// Complejidad O(h), h es la altura del árbol
private int find(int p){
    assert( p >= 0 && p < count );

    // path compression 1
    while( p != parent[p] ){
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;

}

La compresión de ruta anterior no es la forma óptima; podemos comprimir el árbol original como se muestra en la siguiente figura, donde el número de niveles es mínimo.

Este proceso find se puede representar como:

...
// Proceso de búsqueda, encuentra el número de conjunto correspondiente al elemento p
// Complejidad O(h), h es la altura del árbol
private int find(int p) {
    assert (p >= 0 && p < count);

    // Segundo algoritmo de compresión de ruta
    if (p != parent[p])
        parent[p] = find(parent[p]);
    return parent[p];
}
...

Código de ejemplo en Java

Descargar paquete de código fuente:Download

Código del archivo UnionFind3.java:

package ejemplo.union;

/**
* Optimización basada en rango
 */

public class UnionFind4 {

    private int[] rank;   // rank[i] representa el número de niveles del árbol representado por el conjunto con raíz en i
    private int[] parent; // parent[i] representa el nodo padre al que apunta el i-ésimo elemento
    private int count;    // Número de datos

    // Constructor
    public UnionFind4(int count){
        rank = new int[count];
        parent = new int[count];
        this.count = count;
        // Inicialización, cada parent[i] se apunta a sí mismo, indicando que cada elemento forma su propio conjunto
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // Proceso de búsqueda, encuentra el número de conjunto correspondiente al elemento p
    // Complejidad O(h), h es la altura del árbol
    private int find(int p){
        assert( p >= 0 && p < count );
        // Consulta repetidamente 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;

        // Segundo algoritmo de compresión de ruta
        //if( p != parent[p] )
        //parent[p] = find( parent[p] );
        //return parent[p];
    }

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

    // Fusiona los conjuntos a los que pertenecen los elementos p y q
    // Complejidad O(h), 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;

        if( rank[pRoot] < rank[qRoot] ){
            parent[pRoot] = qRoot;
        }
        else if( rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // Mantener el valor de rank
        }
    }
}
Otras extensiones