Union-Find Operationen an einem Baum?

Question

Kann jemand bitte die Antwort in Fettschrift erklären? Wie es gemacht wird?

Unten sehen Sie eine Abfolge von vier Union-Find-Operationen (mit gewichteten-Union- und Vollkomprimierungsoperationen), die zur folgenden Aufwärtsstruktur führten. Was waren die letzten beiden Operationen?

Antwort: Union (D, A), Union (B, C), Union (D/A, B/C), Finden (B/C).

Answer 1

Die Notation wegen der Sets verwendet wird.

Lassen Sie uns die vier Operationen gelten:

Union(D,A) führt zu folgenden Baum:

D 
/
A 

Union(B,C) führt zu folgenden Baum:

B 
/
C 

Jetzt Union(D/A,B/C) bedeutet, dass, weil D und A gehören zu dem gleichen Satz, ist es egal, was die Tannen t Argument ist, kann es D sein oder es kann A sein. Ähnlich, weil B und C zum selben Satz gehören, ist es egal, was das zweite Argument ist, es kann B sein oder es kann C, sein, das Ergebnis wird dasselbe sein.

Das Ergebnis wird nach dritten Betrieb sein:

D 
    /|\ 
A B C 

Wenn die vierte Operation Find(B) ist, die:

D 
/\ 
A B 
     \ 
     C 

Nun, da Kompression auch erlaubt ist, in dem Baum der Find(C) Betrieb führen würde Der Baum würde gleich bleiben, denn wenn wir die Komprimierung nach einer Find-Operation anwenden, machen wir alle Knoten im Pfad bis zum Wurzel-Direkt-Kind des Stammes, aber da wir nicht aufstoßen werden, wir können nicht C sofort Kind von machen, wie es im letzten Baum ist.

Richtige Antwort

Die richtige Reihenfolge von vier Operationen ist:

Union(D,A), Union(B,C), Union(D/A,B/C),Find(C).