Optimierung des Rangs in Union-Find
Im vorherigen Unterabschnitt wurde die größenbasierte Optimierung für die Union-Find-Datenstruktur vorgestellt, aber in bestimmten Szenarien bestehen weiterhin Probleme, wie in der untenstehenden Abbildung gezeigt, wenn die Operation union(4,2) ausgeführt wird.
Gemäß dem vorherigen Unterabschnitt zeigt bei größenbasierter Optimierung die Wurzel der Menge mit weniger Elementen auf die Wurzel der Menge mit mehr Elementen. Nach der Operation beträgt die Anzahl der Ebenen 4, also eine Ebene mehr als zuvor, wie in der untenstehenden Abbildung gezeigt:
Es ist ersichtlich, dass es nicht ganz korrekt ist, sich auf die Größe der Menge zu verlassen, um die Richtung des Zeigers zu bestimmen. Genauer gesagt sollte die Richtung des Wurzelzeigers anhand der Anzahl der Ebenen der beiden Mengen bestimmt werden: Die Wurzel der Menge mit weniger Ebenen zeigt auf die Wurzel der Menge mit mehr Ebenen, wie in der untenstehenden Abbildung gezeigt. Dies ist die rangbasierte Optimierung.
Wir fügen den Eigenschaften der Union-Find-Datenstruktur ein rank-Array hinzu, wobei rank[i] die Anzahl der Ebenen des Baums angibt, der durch die bei i verwurzelte Menge repräsentiert wird.
private int[] rank; // rank[i] steht für die Anzahl der Ebenen des Baums, der durch die bei i verwurzelte Menge dargestellt wird
private int[] parent; // parent[i] steht für den Elternknoten, auf den das i-te Element zeigt
private int count; // Anzahl der Datenelemente
...
Der Konstruktor sollte entsprechend angepasst werden:
// Konstruktor
public UnionFind4(int count){
rank = new int[count];
parent = 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;
rank[i] = 1;
}
}
...
Beim Zusammenführen zweier Elemente ist es notwendig, die Anzahl der Ebenen der Mengen der Wurzelknoten zu vergleichen. Der gesamte Prozess hat O(h)-Komplexität, wobei h die Höhe des Baums ist.
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; // an dieser Stelle verwalte ich den rank-Wert
}
}
...
Java-Beispielcode
Quellpaket herunterladen:Herunterladen
Code der Datei UnionFind3.java:
/**
* Rangbasierte Optimierung
*/
public class UnionFind4 {
private int[] rank; // rank[i] steht für die Anzahl der Ebenen des Baums, der durch die bei i verwurzelte Menge dargestellt wird
private int[] parent; // parent[i] steht für den Elternknoten, auf den das i-te Element zeigt
private int count; // Anzahl der Datenelemente
// Konstruktor
public UnionFind4(int count){
rank = new int[count];
parent = 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;
rank[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;
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; // den Rangwert beibehalten
}
}
}