Union/Znajdź algorytmu bez unii W rankingu dla struktury danych lasy rozłączne ustawiony

Question

Oto podział na unii/znaleźć algorytm rozłącznych zestaw lasach na wikipedia:

• Barebone rozłączne-set lasy ... (O(n))
  • ... z unii w rankingu ... (teraz poprawiła się O(log(n))
    • ... z kompresją ścieżki (teraz poprawiła się O(a(n)) skutecznie O(1))

unii W rankingu Wdrożenie wymaga, aby każdy węzeł utrzymuje pole rank dla celów porównawczych. Moje pytanie brzmi: czy związek według rangi jest wart tej dodatkowej przestrzeni? Co się stanie, jeśli pominiemy związek według rangi i zamiast tego zrobię tylko kompresję ścieżek? Czy to wystarczająco dobre? Jaka jest teraz amortyzowana złożoność?

---

Komentarz składa, że ​​zakłada, że ​​związek o randze bez kompresji ścieżki (zamortyzowanego O(log(n) złożoność) jest wystarczająca dla większości praktycznych zastosowań. To jest poprawne. To, o co pytam, jest odwrotne: co, jeśli pominiesz związek według rangi i TYLKO zrobisz kompresję ścieżek?

W pewnym sensie kompresja ścieżki jest dodatkowym krokiem w celu poprawy unii według rangi i dlatego ten dodatkowy krok można pominąć bez katastrofalnych konsekwencji. Ale czy związek po klasie jest koniecznym pośrednim krokiem do kompresji ścieżki? Czy mogę go pominąć i przejść od razu do kompresji ścieżki, czy może to być katastrofa?

---

Zwrócono również uwagę, że bez związków według rang, powtarzające się związki mogłyby stworzyć strukturę o podobnej strukturze. Oznacza to, że operacja kompresji z pojedynczą ścieżką może w najgorszym przypadku zająć O(n). To oczywiście będzie miało wpływ na przyszłe operacje, więc to, w jaki sposób to się dzieje, gdy amortyzuje się wiele operacji, jest tym, co mnie bardziej interesuje.

Answer 1

google dla „bez unii W rankingu” i drugi link, który wymyślił był this one:

... Zamykamy ten rozdział z krytym analizy unii znalezienia z kompresją ścieżki ale bez związek przez pozycja ...

Związek znalezienia datastructure z kompresją ścieżki ale bez unii wg rankingu procesy m znalezienia i N-1 Link operacje w czasie O ((m + n) log n)

Answer 2

Kompresja ścieżki spłaszcza strukturę drzewa. Unii według rangi pomaga połączyć. Załóżmy, że pominiesz to ostatnie. Teraz masz las bez informacji o rangach, aby wybrać sposób scalenia. Potencjalnie ryzykujesz teraz połączenie drzewa o większej głębokości z mniejszą głębokością, co prowadzi do niezrównoważonej struktury drzewa. W najgorszym przypadku możesz otrzymać listę połączoną. Zwiększa się złożoność czasu twojej Unii, nawet jeśli dla Find pozostaje taka sama.

IMO, lepiej pominąć kompresję ścieżki, ale nie rangować.