Optimisation de la taille Union-Find

En suivant l'approche de la sous-section précédente, nous prenons l'ensemble disjoint tel qu'indiqué dans la figure ci-dessous et effectuons l'opérationunion(4,9).

La structure après l'opération de fusion est :

On peut voir que la hauteur de l'arbre de cette structure est relativement élevée. Si le nombre d'éléments augmente à ce moment, le coût résultant sera relativement important. Résoudre ce problème est en fait très simple : avant d'effectuer l'opération de pointage spécifique, il faut d'abord juger, et pointer la racine de l'ensemble ayant le moins d'éléments vers la racine de l'ensemble ayant le plus d'éléments, ce qui peut générer un arbre de plus faible hauteur avec une probabilité plus élevée.

Lors de la construction de l'ensemble disjoint, un paramètre supplémentaire est nécessaire, le tableausz,sz[i]indique queile nombre d'éléments dans l'ensemble dont la racine est...

// constructeur
public UnionFind3(int count){
    parent = new int[count];
    sz = 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;
        sz[i] = 1;
    }
}

Pendant l'opération de fusion, la direction de la fusion est déterminée en fonction du nombre d'éléments dans les arbres où se trouvent les deux éléments.

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];
    }
}

Après optimisation, le résultat de la fusion est le suivant : 9 pointe vers le nœud parent 8.

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier UnionFind3.java :

package example.union;

/**
* Optimisation de la taille de l'ensemble Union-Find
 */
public class UnionFind3 {
    // parent[i] représente le nœud parent du i-ème élément
    private int[] parent;
    // sz[i] représente le nombre d'éléments dans l'ensemble dont la racine est i
    private int[] sz;
    // nombre d'éléments de données
    private int count;

    // constructeur
    public UnionFind3(int count){
        parent = new int[count];
        sz = 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;
            sz[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;
        // Déterminer la direction de fusion en fonction du nombre d'éléments dans les arbres où se trouvent les deux éléments
        // Fusionner l'ensemble avec moins d'éléments dans l'ensemble avec plus d'éléments
        if( sz[pRoot] < sz[qRoot] ){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}
autres extensions