Warum berücksichtigt der gewichtete Quick Union-Algorithmus die Größe des Baums statt ihrer Höhe?
Ich habe Robert Sedgewicks Video über Verbesserungen der schnellen Union angeschaut. ( Ссылка )
Dort verwendet er die Größe des Baumes und nicht die Höhe. Das Problem besteht eigentlich darin, den Wurzelknoten zu finden. Das Finden wird schwierig sein, wenn die Höhe hoch ist. Also sollten wir einen Weg finden, den Effekt der Höhe zu mildern. Nur wenn wir Höhen vergleichen, wird es nicht wie erwartet funktionieren. Wird ein kürzerer Baum mit einem höheren Baum verbunden, kann das Problem nicht gelöst werden, sondern: Verbinden eines Baums mit einer kleineren Anzahl von Knoten mit einem Baum mit einer größeren Anzahl von Knoten?
Was ist mit dem folgenden Fall?
entsprechend der Logik im Video:
Größe von A tree = 4
Größe des B-Baums = 7
und wenn Sie A mit B verbinden. tatsächlich machen wir den resultierenden Baum größer (Höhe 4). Aber hätten wir es basierend auf Baumhöhen gemacht, hätten wir es lösen können, indem wir Baum B mit A verbinden. und so wird der resultierende Baum die Höhe 3 haben.
Habe ich Recht? Wenn falsch, wo liege ich falsch?
1 Antwort
Beachten Sie, dass die meisten Implementierungen einer nicht zusammengesetzten Gesamtstruktur die Pfadkomprimierung -Optimierung anwenden, bei der Sie bei jeder Suche die übergeordneten Zeiger aller Knoten in der Kette so ändern, dass sie alle enthalten zeigen Sie auf ihren Vertreter.
Es stellt sich heraus, dass, wenn Sie Pfadkompression verwenden und die Höhen aller Knoten vor der Komprimierung verfolgen, dann die asymptotische Leistung der Verknüpfung nach Höhe (normalerweise Einheit-nach-Rang genannt) , wobei der "Rang" die Höhe vor irgendwelchen Kompressionen ist und die Gewichtsverknüpfung identisch ist. Beides ergibt die inverse Ackermann-Zeitkomplexität. Dieses Ergebnis kommt von diesem Papier , das sehr technisch ist, aber beide Ergebnisse beweist. p>
Auch wenn Sie das nicht tun, gibt es einen anderen Weg zu sehen, dass diese beiden Ansätze (in etwa) gleich sind. Beachten Sie, dass wenn Sie einen Baum der Höhe eins haben, er mindestens zwei Knoten haben muss. Warum? Nun, die einzige Möglichkeit, einen Baum der Höhe eins zu machen, besteht darin, mit Bäumen der Höhe Null zu verschmelzen, von denen jeder mindestens einen Knoten haben muss. Mit ähnlicher Logik können Sie sehen, dass, wenn Sie einen Baum der Höhe zwei haben, er mindestens vier Knoten haben muss, denn um ihn zu bilden, mussten Sie zwei Bäume der Höhe eins zusammenführen. Allgemeiner können Sie zeigen, dass ein Baum der Höhe n mindestens 2 n Knoten haben muss. Daher ist das Zusammenführen nach Höhe im Wesentlichen dasselbe wie das Zusammenführen nach Gewicht, da eine enge Verbindung zwischen den Höhen und den Größen der Bäume besteht.
Hoffe, das hilft!
Tags und Links algorithm graph-algorithm data-structures union-find