Optimisation du rang dans Union-Find
La sous-section précédente a introduit l'optimisation basée sur la taille pour la structure de données Union-Find, mais dans certains scénarios, certains problèmes subsistent, comme le montre la figure ci-dessous, en effectuant l'opération union(4,2).
Selon la sous-section précédente, avec l'optimisation basée sur la taille, la racine de l'ensemble ayant moins d'éléments pointe vers la racine de l'ensemble ayant plus d'éléments. Après l'opération, le nombre de niveaux devient 4, soit un niveau de plus qu'avant, comme le montre la figure ci-dessous :
On peut voir que se fier à la taille de l'ensemble pour déterminer la direction du pointeur n'est pas entièrement correct. Plus précisément, la direction du pointeur de racine doit être déterminée en fonction du nombre de niveaux des deux ensembles : la racine de l'ensemble ayant moins de niveaux pointe vers la racine de l'ensemble ayant plus de niveaux, comme le montre la figure ci-dessous. Il s'agit de l'optimisation basée sur le rang.
Nous ajoutons un tableau rank aux propriétés de la structure de données Union-Find, où rank[i] représente le nombre de niveaux de l'arbre représenté par l'ensemble dont la racine est i.
private int[] rank; // rank[i] représente le nombre de niveaux de l'arbre représenté par l'ensemble ayant pour racine i
private int[] parent; // parent[i] représente le nœud parent vers lequel pointe le i-ème élément
private int count; // nombre d'éléments de données
...
Le constructeur doit être modifié en conséquence :
// constructeur
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// initialisation, chaque parent[i] pointe vers lui-même, indiquant que chaque élément forme un ensemble à lui seul
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
...
Lors de la fusion de deux éléments, il est nécessaire de comparer le nombre de niveaux des ensembles des nœuds racines. L'ensemble du processus a une complexité O(h), où h est la hauteur de l'arbre.
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; // à ce stade, je maintiens la valeur de rank
}
}
...
Exemple de code Java
Téléchargement du paquet source :Télécharger
Code du fichier UnionFind3.java :
/**
* Optimisation basée sur le rang
*/
public class UnionFind4 {
private int[] rank; // rank[i] représente le nombre de niveaux de l'arbre représenté par l'ensemble ayant pour racine i
private int[] parent; // parent[i] représente le nœud parent vers lequel pointe le i-ème élément
private int count; // nombre d'éléments de données
// constructeur
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// initialisation, chaque parent[i] pointe vers lui-même, indiquant que chaque élément forme un ensemble à lui seul
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// processus find, trouver le numéro de l'ensemble correspondant à l'élément p
// complexité O(h), h est la hauteur de l'arbre
private int find(int p){
assert( p >= 0 && p < count );
// continuer à interroger le nœud parent jusqu'à atteindre le nœud racine
// caractéristique du nœud racine : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// vérifier si l'élément p et l'élément q appartiennent au même ensemble
// complexité O(h), h est la hauteur de l'arbre
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// fusionner les ensembles contenant l'élément p et l'élément q
// complexité O(h), h est la hauteur de l'arbre
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; // maintenir la valeur de rank
}
}
}