Optimización de rank en Union-Find
La sección anterior presentó la optimización basada en size de Union-Find, pero en algunos escenarios también existen ciertos problemas, como se muestra en la siguiente figura, la operación union(4,2).
Según la sección anterior, en la optimización de size, la raíz del conjunto con menos elementos apunta a la raíz del conjunto con más elementos. Después de la operación, el número de niveles se convierte en 4, un nivel más que antes, como se muestra en la siguiente figura:
De esto se deduce que confiar en el size del conjunto para determinar la dirección no es del todo correcto; más precisamente, se debe determinar la dirección de la raíz según el número de niveles de los dos conjuntos: la raíz del conjunto con menos niveles apunta a la raíz del conjunto con más niveles, como se muestra en la siguiente figura. Esta es la optimización basada en rank.
Añadimos el array rank a los atributos del Union-Find, donde rank[i] representa el número de niveles del árbol representado por el conjunto cuya raíz es i.
private int[] rank; // rank[i] representa el número de niveles del árbol representado por el conjunto cuya raíz es i.
private int[] parent; // parent[i] representa el nodo padre al que apunta el elemento i-ésimo.
private int count; // Número de elementos
...
El constructor se modifica en consecuencia:
// Constructor
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// Inicialización, cada parent[i] apunta a sí mismo, lo que indica que cada elemento forma un conjunto por sí mismo.
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
...
Al fusionar dos elementos, es necesario comparar los niveles de los conjuntos de los nodos raíz; todo el proceso tiene 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;
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; // En este momento, mantenemos el valor de rank.
}
}
...
Código de ejemplo en Java
Descarga del paquete de código fuente:Download
Código del archivo UnionFind3.java:
/**
* Optimización basada en rank
*/
public class UnionFind4 {
private int[] rank; // rank[i] representa el número de niveles del árbol representado por el conjunto cuya raíz es i.
private int[] parent; // parent[i] representa el nodo padre al que apunta el elemento i-ésimo.
private int count; // Número de elementos
// Constructor
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// Inicialización, cada parent[i] apunta a sí mismo, lo que indica que cada elemento forma un conjunto por sí mismo.
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// Proceso de búsqueda, busca 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;
}
// Verifica 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.
}
}
}