Union-Find-Größenoptimierung

Nach dem Ansatz aus dem vorherigen Unterabschnitt nehmen wir das Disjoint-Set wie in der folgenden Abbildung gezeigt und führen dieunion(4,9)Operation aus.

Die Struktur nach der Merge-Operation ist:

Es ist zu erkennen, dass die Baumhöhe dieser Struktur relativ hoch ist. Wenn die Anzahl der Elemente zu diesem Zeitpunkt zunimmt, sind die resultierenden Kosten relativ groß. Dieses Problem zu lösen ist eigentlich sehr einfach: Bevor die konkrete Verweisoperation ausgeführt wird, wird zuerst geprüft, und die Wurzel der Menge mit weniger Elementen wird auf die Wurzel der Menge mit mehr Elementen verwiesen, wodurch mit höherer Wahrscheinlichkeit ein Baum mit geringerer Höhe erzeugt werden kann.

Beim Aufbau des Disjoint-Set wird ein weiterer Parameter benötigt,szArray,sz[i]gibt an, dassidie Anzahl der Elemente in der Menge mit Wurzel ...

// Konstruktor
public UnionFind3(int count){
    parent = new int[count];
    sz = new int[count];
    this.count = count;
    // Initialisierung: Jedes parent[i] zeigt auf sich selbst, was bedeutet, dass jedes Element eine eigene Menge bildet
    for( int i = 0 ; i < count ; i ++ ){
        parent[i] = i;
        sz[i] = 1;
    }
}

Während der Merge-Operation wird die Richtung der Zusammenführung anhand der Anzahl der Elemente in den Bäumen, in denen sich die beiden Elemente befinden, bestimmt.

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

Nach der Optimierung lautet das Zusammenführungsergebnis wie folgt: 9 zeigt auf den Elternknoten 8.

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Code der Datei UnionFind3.java:

package example.union;

/**
* Größenoptimierung der Union-Find-Menge
 */
public class UnionFind3 {
    // parent[i] repräsentiert den Elternknoten des i-ten Elements
    private int[] parent;
    // sz[i] gibt die Anzahl der Elemente in der Menge an, deren Wurzel i ist
    private int[] sz;
    // Anzahl der Datenelemente
    private int count;

    // Konstruktor
    public UnionFind3(int count){
        parent = new int[count];
        sz = new int[count];
        this.count = count;
        // Initialisierung: Jedes parent[i] zeigt auf sich selbst, was bedeutet, dass jedes Element eine eigene Menge bildet
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            sz[i] = 1;
        }
    }

    // find-Prozess, finde die Mengennummer, die dem Element p entspricht
    // O(h)-Komplexität, h ist die Höhe des Baums
    private int find(int p){
        assert( p >= 0 && p < count );
        // den Elternknoten weiter abfragen, bis der Wurzelknoten erreicht ist
        // Eigenschaft des Wurzelknotens: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }

    // prüfen, ob Element p und Element q zu derselben Menge gehören
    // O(h)-Komplexität, h ist die Höhe des Baums
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // die Mengen, die Element p und Element q enthalten, zusammenführen
    // O(h)-Komplexität, h ist die Höhe des Baums
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        // Bestimme die Zusammenführungsrichtung anhand der Anzahl der Elemente in den Bäumen, in denen sich die beiden Elemente befinden
        // Die Menge mit weniger Elementen in die Menge mit mehr Elementen zusammenführen
        if( sz[pRoot] < sz[qRoot] ){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}
Weitere Erweiterungen