Union/finden Algorithmus ohne Vereinigung von Rang für disjunkte Satz Wälder Datenstruktur

Question

Hier ist eine Aufteilung auf die Vereinigung/finden Algorithmus für disjunkte Satz Wälder auf wikipedia:

• Barebone disjoint-Set Wälder ... (O(n))
  • ... mit Vereinigung von Rang ... (jetzt O(log(n)) verbesserte
    • ... mit Pfadkompression (jetzt O(a(n)) verbessert, effektiv 012.)

nach Rang Implementieren Union erfordert, dass jeder Knoten ein rank Feld zu Vergleichszwecken hält. Meine Frage ist, ist Union um Rang diesen zusätzlichen Raum wert? Was passiert, wenn ich die Vereinigung nach Rang überspringe und stattdessen nur die Pfadkomprimierung vornehme? Ist es gut genug? Wie hoch ist die amortisierte Komplexität?

---

Ein Kommentar wird das bedeutet, dass Vereinigung von Rang ohne Pfad Kompression (O(log(n) Komplexität abgeschrieben) ist für die meisten praktische Anwendung ausreichend. Das ist richtig. Was ich frage, ist umgekehrt: Was passiert, wenn Sie die Vereinigung nach Rang überspringen und NUR die Pfadkomprimierung durchführen?

In gewisser Hinsicht ist die Pfadkomprimierung ein zusätzlicher Schritt, um die Vereinigung nach Rang zu verbessern, und deshalb kann dieser zusätzliche Schritt ohne verhängnisvolle Konsequenzen ausgelassen werden. Aber ist Union nach Rang ein notwendiger Zwischenschritt zur Pfadkompression? Kann ich es überspringen und direkt zur Pfadkompression wechseln, oder wird das katastrophal sein?

Es wurde auch darauf hingewiesen, dass wiederholte Vereinigungen ohne eine Vereinigung nach Rang eine Linked-List-ähnliche Struktur erzeugen könnten. Dies bedeutet, dass eine Single-Path-Kompressionsoperation im schlimmsten Fall O(n) dauern könnte. Dies würde sich natürlich auf zukünftige Operationen auswirken. Wie sich das auswirkt, wenn es über viele Operationen amortisiert wird, interessiert mich mehr.

Answer 1

Ich googeln für „ohne Vereinigung von Rang“ und die zweite Verbindung, die oben kam, war this one:

... Wir schließen diesen Abschnitt mit einer Analyse der Vereinigungs-Suche mit Pfad Kompression aber ohne Union von Rang ...

Die Vereinigungs-Suche Datenstruktur mit Pfad Kompression aber ohne Vereinigung von Rang Prozesse m finden und n-1 Link Operationen in der Zeit O ((m + n) log n)

Answer 2

Pfadkomprimierung flacht die Baumstruktur ab. Vereinigung nach Rang hilft zu verschmelzen. Angenommen, Sie überspringen das letztere. So, jetzt haben Sie einen Wald ohne Ranginformationen zu wählen, wie Sie zusammenführen. Möglicherweise besteht nun die Gefahr, dass ein Baum mit einer größeren Tiefe mit einer kleineren Tiefe verschmolzen wird - was zu einer unausgeglichenen Baumstruktur führt. Im schlimmsten Fall haben Sie möglicherweise eine verkettete Liste. Die amortisierte Zeitkomplexität Ihrer Union steigt, selbst wenn diese für Find gleich bleibt.

IMO, Es wäre besser, Pfadkomprimierung zu überspringen, aber keinen Rang.