ScanImage013 (5)

1.3. ALGORYTMY WYSZUKIWANIA I SCALANIA ggaa 8888B as» ma aawt bws*

(0 + 1 + ... + n - l)/n = (/; - l)/2.

Teraz załóżmy, źe wszystkie pozostałe pary definiują połączenia obiektu n z jakimś innym. Operacja wyszukiwania dla każdej z tych par wymaga przejrzenia przynajmniej n-1 wskaźników. Suma całkowita dla m operacji wyszukiwania przy takiej sekwencji par wejściowych jest z pewnością większa niż mnt2.    ■

Na szczęście istnieje prosta modyfikacja tego algorytmu gwarantująca, że nie zdarzą się tak niekorzystne przypadki jak ten omówiony powyżej. Zamiast w ramach operacji scalania a priori łączyć drugie drzewo z pierwszym, należy przechowywać liczbę węzłów każdego drzewa i zawsze dołączać mniejsze drzewo do większego. Zaimplementowanie tej zmiany wymaga nieco więcej kodu i jeszcze jednej tablicy na przechowywanie liczników węzłów (patrz program 1.3), ale prowadzi do znacznej poprawy' wydajności całego algorytmu. Tę poprawioną wersję będziemy nazywali algorytmem zrównoważonego szybkiego scalania.

Na rysunku 1.7 pokazano las drzew' skonstruowanych przez algorytm zrównoważonego szybkiego scalania dla danych przykładowych z rysunku 1.1. Nawet dla tego małego przykładu ścieżki w^r drzew ach są znacznie krótsze niż w niezrównoważonej wersji z rysunku 1.5. Rysunek l .8 pokazuje, co się dzieje w przypadku najgorszym. kiedy wielkości zbiorów scalanych w' trakcie operacji scalania sązaw^fsze równe (i są potęgami 2). Te trzy struktury wyglądają na skomplikowane, ale mają prostą własność: maksymalna liczba wskaźników', które trzeba przejść, aby dostać się do korzenia drzewa o 2" węzłach, wynosi n. Ponadto scalając dwa drzewa o 2* węzłach, otrzymujemy drzewo o węzłach, a maksymalną odległość do korzenia zwiększamy o jeden, czyli do n-1- /. Na tej obserwacji można oprzeć dowód, że algorytm zrównoważony jest istotnie bardziej efektywny niż niezrównoważony.

Twierdzenie 1.3. Algorytm zrównoważonego szybkiego scalania wymaga przejścia najwyżej Ig n wskaźników, aby stwierdzić, czy dowolne dwa z n obiektów są połączone.

p	Q	0	1	2	3	4	5	6	7	8	9
3	4	0	1	2	4	4	5	6	7	8	9
4	9	0	1	2	4	9	5	6	7	8	9
8	0	0	1	2	4	9	5	6	7	0	9
2	3	0	1	9	4	9	5	6	7	0	9
5	6	0	1	9	4	9	6	6	7	0	9
2	9	0	1	9	4	9	6	6	7	0	9
5	9	0	1	9	4	9	6	9	7	0	9
7	3	0	1	9	4	9	6	9	9	0	9
4	8	0	1	9	4	9	6	9	9	0	0
5	6	0	1	9	4	9	6	9	9	0	0
0	2	0	1	9	4	9	6	9	9	0	0
6	1	i^-	1	9	4	9	6	9	9	0	0
5	8	1	1	9	4	9	6	9	9	0	0

Rysunek 1.6

Przykład szybkiego scalania (I niezbyt szybkiego wyszukiwania)

Powyższa sekwencja obrazuje zawartość tablicy id po każdym odczytaniu pary wy mienionej w lewej kolumnie i przetworzeniu jej przez algorytm szybkiego scalania (program 1.2). Szarym kolorem oznaczono elementy zmieniane na skutek operacji scalania (jednej na jedną parę). Przetwarzanie pary p-q polega na prześledzeniu łańcucha wskaźników wychodzących od p do elementu i., dla którego id [ i'—i; prześledzeniu łańcucha wskaźników wychodzących od q do elementu j. dla którego    •

porównaniu i z j. Jeżeli elementy okażą się różne, należy użyć przypisania id (i j -id (j ]. W przypadku operacji wyszukiwania dla pary 5-8 (ostatni wiersz), przyjmuje warto-ści5 6 9 0 1,a)-wartościs 0 l.

15-S8K I