Informatyka MIMUW

Alternatywna implementacja to las zbiorów rozłącznych, w którym każde drzewo odpowiada jednemu ze zbiorów z naszej rodziny. Z każdym elementem zbioru jest związany wskaźnik do pewnego innego elementu (jego ojca w drzewie). Wyjątek stanowi reprezentant zbioru (a zarazem korzeń drzewa), którego wskaźnik wskazuje na niego samego. Operacja MakeSet tworzy jednoelementowe drzewo z korzeniem wskazującym na samego siebie. Operacja Union polega na przestawieniu wskaźnika jednego reprezentanta tak, by wskazywał na drugiego. Koszt obydwu tych operacji to oczywiście O(1). <

Operacja Find polega na przejściu po wskaźnikach ścieżki od danego węzła do reprezentanta (czyli korzenia). Jej koszt jest proporcjonalny do głębokości danego węzła w drzewie. Nietrudno podać przykład ciągu operacji, który powoduje powstanie drzewa w kształcie listy, czyli pesymistyczny koszt takiej operacji Find to \( \Theta(n) \) dla rodziny zbiorów zawierającej łącznie n elementów.

Łączenie według wysokości

Podobną do stosowanego dla list "łączenia z wyważaniem" metodą można zapewnić lepsze ograniczenie kosztu operacji Find. W korzeniu każdego drzewa przechowujemy dodatkowy atrybut - jego wysokość - i podczas operacji Union zawsze przyłączamy niższe drzewo do wyższego (remisy rozstrzygając dowolnie). Koszt Union pozostaje stały, a nietrudno pokazać, że teraz wysokość drzewa jest co najwyżej logarytmiczna względem jego rozmiaru, skąd wynika, że pesymistyczny koszt operacji Find to \( O(\lg n) \).

Kompresja ścieżki

Równie prosta, a bardzo skuteczna heurystyka polega na tym, że w ramach operacji Find po wyznaczeniu korzenia v drzewa zawierającego węzeł x przebiegamy ponownie ścieżkę od x do v i przyłączamy wszystkie napotkane węzły bezpośrednio do v. Dzięki temu późniejsze operacje Find dotyczące węzłów na ścieżce od x do v oraz ich potomków będą kosztowały mniej.

Przy stosowaniu kompresji ścieżki utrzymywanie poprawnych wartości atrybutu "wysokość" wykorzystywanego podczas wykonywania Union byłoby zbyt kosztowne. Zamiast tego będziemy przechowywać w węzłach atrybut "ranga", który będziemy wykorzystywać i modyfikować dokładnie tak samo, jak atrybut "wysokość" przy łączeniu według wysokości: podczas operacji Union przyłączamy drzewo o niższej randze do drzewa o wyższej randze, a w przypadku remisu po przyłączeniu zwiększamy rangę korzenia o 1. Tak więc ranga stanowi górne ograniczenie wysokości drzewa, a w myśl zadania 3 jej wartość nie przekracza \( \lfloor\lg n\rfloor \) dla rodziny zbiorów zawierającej łącznie n elementów. Poniższy lemat wylicza kilka dalszych użytecznych własności rang:

Lemat Lemat 1

W lesie zbiorów rozłącznych z łączeniem według rangi i kompresją ścieżek

(a) ranga węzła, który nie jest korzeniem, jest mniejsza (ściśle) niż ranga jego ojca;

(b) zawsze kiedy ojciec danego węzła się zmienia, to nowy ojciec ma większą rangę niż stary;

(c) jeśli ranga reprezentanta pewnego zbioru jest równa r, to rozmiar tego zbioru wynosi co najmniej \( 2^r \);

(d) jeśli zbiory zawierają łącznie \( n \) elementów, to jest co najwyżej \( n/2^r \) węzłów rangi r, dla dowolnego \( r\ge 0 \). Dowód lematu pozostawiamy jako ćwiczenie.

Zanim przystąpimy do analizy kosztu opisanych wyżej operacji, zdefiniujemy dwie funkcje: jedną bardzo szybko rosnącą i drugą, rosnącą bardzo wolno. Niech \( F(0) = 1 \),

\( F(k) = 2^{2^{.^{.^{.^2}}\Big\}k}} = 2^{F(k-1)} \) dla k>0.

Oto kilka pierwszych wartości funkcji F:

Jak widać, funkcja F rośnie bardzo szybko.

Funkcję logarytm iterowany definiuje się następująco: \( G(n) = \lg^* n = \min\{k:F(k)\ge n\} \). Oto tabelka początkowych wartości funkcji G:

Funkcja G rośnie niesłychanie wolno i dla wszystkich n mających jakiekolwiek praktyczne znaczenie nie przekracza wartości 5.

Na potrzeby analizy kosztu zamortyzowanego operacji na lesie zbiorów rozłącznych przyporządkujemy każdy węzeł do jednego z ponumerowanych bloków: jeśli mianowicie dany węzeł ma rangę r, to przyporządkowujemy go do bloku o numerze \( \lg^* r \). Ponieważ rangi węzłów mieszczą się w zakresie od 0 do \( \lfloor \lg n\rfloor \), mamy \( \lg^* n \) bloków o numerach od 0 do \( \lg^* \lfloor \lg n\rfloor = \lg^*n -1 \). Możemy juz udowodnić

Twierdzenie 2 (Hopcroft, Ullman [HU])

W lesie zbiorów rozłącznych z łączeniem według rangi i kompresją ścieżki koszt m operacji, spośród których n to operacje MakeSet, wynosi \( O(m\lg^* n) \).

Dowód: Ponieważ operacje MakeSet i Union mają koszt stały, wystarczy oszacować łączny koszt m operacji Find. Koszt operacji Find(x) jest proporcjonalny do liczby węzłów na ścieżce od x do korzenia (przed kompresją). Rozbijemy koszt każdej takiej operacji na składniki, które zaksięgujemy do różnych pul. Sumując pule, dostaniemy łączny koszt wszystkich operacji Find.

Dla wierzchołka v leżącego na ścieżce od x do korzenia:

Przypadek 1: Jeśli v lub jego ojciec jest korzeniem, to jednostkę kosztu księgujemy do puli KONIEC_ŚCIEŻKI;

Przypadek 2: Jeśli v i ojciec v są w różnych blokach, to jednostkę kosztu księgujemy do puli ZMIANA_BLOKU;

Przypadek 3: Jeśli v i ojciec v sa w tym samym bloku, to jednostkę kosztu księgujemy do puli TEN_SAM_BLOK.

Przypadek 1 dla każdej operacji Find występuje co najwyżej dwukrotnie, więc łączna zawartość puli KONIEC_ŚCIEŻKI to co najwyżej 2m. Podczas pojedynczej operacji Find przypadek 2 może wystąpić co najwyżej \( \lg^* n-1 \) razy (bo jest nie więcej niż \( \lg^*n \) różnych bloków, a w myśl lematu 1(a) rangi na ścieżce do korzenia tworzą ciąg rosnący). Zatem łączna zawartość puli ZMIANA_BLOKU to \( O(m\lg^* n) \).

Pozostaje nam zatem oszacować zawartość puli TEN_SAM_BLOK. Jeśli v jest w bloku o numerze \( g>0 \), przypadek 3 może dla niego zajść co najwyżej \( F(g)-F(g-1) \) razy (wynika to z lematu 1(b): ranga ojca v za każdym razem rośnie, a kiedy v i ojciec v znajdą się w różnych blokach, to dla v już do końca będzie zachodził przypadek 2 lub 1). Dla v należącego do bloku \( g=0 \) przypadek 3 może zajść co najwyżej raz.

Na mocy lematu 1(d) liczbę węzłów w bloku \( g>0 \) można oszacować z góry przez

\( \displaystyle\sum_{r=F(g-1)+1}^{F(g)} n/2^r\le n/2^{F(g-1)+1}(1+1/2+1/4+\cdots)\le n/2^{F(g-1)}=n/F(g) \)

skąd łączny wkład do puli TEN_SAM_BLOK pochodzący od węzłów z bloku \( g>0 \) szacuje się z góry przez \( (F(g)-F(g-1))\cdot n/F(g)\le n \) (to ostatnie oszacowanie jest prawdziwe również dla \( g=0 \)). Sumując po g, dostajemy górne oszacowanie zawartości puli TEN_SAM_BLOK \( O(n\lg^* n) \).

Uwaga: Wynikające z powyższego twierdzenia oszacowanie kosztu zamortyzowanego operacji Find \( O(\lg^* n) \) można poprawić! Robert Tarjan [T1,T2] podał asymptotycznie optymalne oszacowanie tego kosztu przez tzw. funkcyjną odwrotność funkcji Ackermanna, rosnącą jeszcze wolniej niż funkcja \( \lg^* \). Przystępny opis górnego oszacowania (chociaż znacznie bardziej skomplikowany niż powyższy dowód) można znaleźć w książce [CLRS].