Union–find prawie spłaszcza las za każdym pytaniem
Struktura union–find przechowuje podział elementów na rozłączne zbiory i odpowiada na pytania typu „czy te dwa elementy należą już do tej samej grupy?”. W wersji drzewiastej każdy zbiór ma reprezentanta. Dwie proste heurystyki zmieniają wydajność radykalnie: union by rank dołącza płytsze drzewo pod głębsze, a path compression podczas wyszukiwania reprezentanta przepina odwiedzone węzły bliżej korzenia. Robert Tarjan wykazał dla odpowiednio zorganizowanej sekwencji operacji koszt związany z odwrotnością funkcji Ackermanna — funkcją rosnącą tak wolno, że w praktycznych rozmiarach zachowuje się niemal jak stała. Struktura przyspiesza więc sama siebie w trakcie używania.
Zbiory jako las drzew
Union–find, nazywany też disjoint-set union, obsługuje dwie podstawowe operacje. `find(x)` mówi, który zbiór zawiera x, zwracając jego reprezentanta. `union(a,b)` scala dwa zbiory. Naturalna implementacja reprezentuje każdy zbiór jako drzewo: węzły wskazują rodziców, a korzeń jest reprezentantem.
Bez dodatkowych reguł drzewa mogą zrobić się wysokie. Jeśli kolejne uniony zawsze tworzą długi łańcuch, `find` musi przejść przez wiele rodziców. Problem jest więc podobny do struktur drzewiastych w ogóle: samo poprawne połączenie elementów nie gwarantuje szybkiego dojścia do korzenia.
Union by rank zapobiega łatwemu tworzeniu wysokich drzew
Pierwsza heurystyka mówi: podczas łączenia dwóch drzew dołącz korzeń „mniejszego” lub płytszego drzewa pod korzeń większego. W popularnej wersji utrzymuje się rangę będącą przybliżeniem wysokości. Dzięki temu wysokie struktury nie są bez potrzeby wieszane pod niskimi, co ogranicza wzrost głębokości.
Sama ta technika już daje dobre granice. Prawdziwie niezwykły efekt pojawia się jednak po dodaniu kompresji ścieżki. W `find(x)` i tak odwiedzamy wszystkich przodków od x do korzenia. Po poznaniu reprezentanta możemy przepiąć te węzły bezpośrednio albo bardzo blisko korzenia. Następne zapytania przejdą znacznie krótszą drogę.
Każde wyszukiwanie może przebudować strukturę na przyszłość
Path compression jest ciekawa, bo operacja nie tylko odpowiada na pytanie. Wykorzystuje okazję do poprawienia danych. Jeśli ścieżka x→a→b→c→root została właśnie przejrzana, wszystkie te węzły można skierować wprost do root. Koszt obecnego wyszukiwania zostaje więc częściowo „zainwestowany” w przyspieszenie przyszłych wyszukiwań.
Nie oznacza to, że pojedyncza operacja ma absolutnie stały najgorszy czas. Analiza dotyczy kosztu zamortyzowanego całej sekwencji. Niektóre wywołania mogą przejść dłuższą ścieżkę, ale tak mocno ją przy tym spłaszczają, że podobnie droga praca nie będzie powtarzana bez końca.
Pojawia się odwrotność jednej z najszybciej rosnących funkcji
Robert Tarjan w pracy z 1975 roku analizował sekwencje operacji FIND i UNION i uzyskał granice zawierające funkcję związaną z odwrotnością funkcji Ackermanna. Sama funkcja Ackermanna rośnie niezwykle szybko; jej odwrotność rośnie więc niewiarygodnie wolno. W praktycznych rozmiarach danych wartość tej funkcji pozostaje bardzo mała.
Stąd popularne określenie, że union–find z union by rank i path compression ma operacje „prawie stałoczasowe” w sensie amortyzowanym. Precyzyjnie nie jest to zwykłe O(1), ale dla realistycznych n różnica jest często czysto teoretyczna. To jeden z najbardziej zaskakujących wyników w podstawowych strukturach danych.
Gdzie taki mechanizm jest potrzebny
Union–find świetnie nadaje się do problemów, w których połączenia tylko dochodzą, a my wielokrotnie pytamy o spójność. Algorytm Kruskala używa tej struktury, aby szybko sprawdzać, czy dodanie krawędzi połączy dwa różne komponenty, czy stworzy cykl. Podobny schemat występuje w grupowaniu, śledzeniu komponentów i niektórych algorytmach grafowych.
Najbardziej elegancka jest jednak sama zasada projektowa: struktura danych może modyfikować się podczas odczytu, jeżeli ta modyfikacja zachowuje znaczenie logiczne i przyspiesza kolejne operacje. `find` jest więc jednocześnie pytaniem i zabiegiem konserwacyjnym na strukturze.
Union–find jest niezwykle szybki właśnie dlatego, że rozwiązuje węższy problem
Struktura świetnie obsługuje operacje łączenia zbiorów i pytania o wspólny reprezentant, ale nie jest ogólnym dynamicznym grafem. Klasyczny model nie oferuje równie prostej operacji „cofnij union” ani usunięcia dowolnej krawędzi i natychmiastowego rozdzielenia komponentu. Kompresja ścieżek wręcz zaciera historię, przepinając węzły bezpośrednio do reprezentanta. To nie wada implementacji, lecz świadome wykorzystanie monotonii problemu: zbiory mogą się tylko scalać. Dzięki temu algorytm może agresywnie upraszczać strukturę i osiągać niezwykłą granicę amortyzowaną. Jeśli aplikacja potrzebuje dowolnych usunięć i zapytań o spójność po usunięciu, trzeba użyć bogatszych i zwykle bardziej kosztownych struktur. Wyjątkowa szybkość często wynika z wykorzystania ograniczeń modelu, nie z rozwiązania wszystkiego naraz.