ScanImage015 (5)

1.3 ALGORYTMY WYSZUKIWANIA I SCALANIA ssą- wt &s& mt mi

Program 1.3. Zrównoważona wersja szybkiego scalania

Ten program jest modyfikacją algorytmu szybkiego scalania (patrz program 1.2), w której zastosowano dodatkową tablicę sz, przeznaczoną na przechowywanie dla każdego obiektu o własności id [ i ]    liczby węzłów jego drzewa, po to aby operacja scalania

mogła polegać na dołączaniu zawsze mniejszego z dwóch drzew do większego. Taka modyfikacja zapobiega zbędnemu i wpływającemu ujemnie na wydajność rozrostowi ścieżek w drzewie.

iłinclude <icstream.h> static const ir.t n-10000; int nain(>

{ int i, j, p, q, id[n], sz[n); for (i - 0; i < n; i++)

{ idti3 - i; sz[iJ - 1; } while (cin » p » q)

{

for (i - p; i 1= id li]; i = id C i]>; for (j - q; j != id[jj; j = id[j]); if (i == j) continue; if (sz[i] < sz[j])

l id[il = j; szlj! +* sz[i 1; ) eise

{ idlj] - i; sz[il +- sz[j]; } cout « " •' << p « *' " << q « endl;

}

} żników (jak to było w algorytmie szybkiego wyszukiwania). Do ideału możemy się zbliżyć wówczas, gdy każdy sprawdzany węzeł zmodyfikujemy tak, by wskazywał wprost na korzeń. Krok laki może się na pierwszy rzut oka wydawać drastyczny, ale jest prosty do zrealizowania, a struktura drzew' nie jest żadną świętością, której nic można by naruszać. Jeżeli możemy ją zmodyfikować, aby uzyskać bardziej wydajny algorytm, powinniśmy to zrobić. Metoda ta jest nazywana kompresją ścieżek. Można ją łatwo zaimplementować, dodając jeszcze jeden przebieg przez każdą ścieżkę w operacji scalania i przypisując elementom tablicy id odpowiadającym każdemu napotkanemu na drodze wierzchołkowi wskazanie na korzeń. Wynik ostateczny będzie polegał na prawne całkowitym spłaszczeniu drzew, aproksymującym idealny przypadek osiągany przez algorytm szybkiego wyszukiwania (patrz rysunek 1.9). Analiza, z której ten fakt wynika, jest bardzo skomplikowana, ale sama metoda jest prosta i efektywna. Na rysunku 1.11 pokazano wyniki otrzymywane z kompresji ścieżek na dużym przykładzie.

Istnieje wiele innych sposobów-' zaimplementowania kompresji ścieżek. Na przykład program 1.4 jest implementacją, w której ścieżki są kompresowane tak, aby każde łącze prowadziło do następnego węzła w ścieżce na drodze w górę drzew-a, jak pokazano na rysunku 1.10. Metoda ta jest nieco prostsza w realizacji niż pełna kompresja ścieżek (patrz zadanie 1.16) i pozwala osiągnąć ten sam wynik ogólny. Tę odmianę algorytmu będziemy nazywać zrównoważonym

17