ScanImage011 (5)

1.3. ALGORYTMY WYSZUKIWANIA I SCALANIA im 88SSS 3®33 J8838 SSW 33S&

kiego scalania, zrealizowaną na przykładzie danych z rysunku 1.1. Natomiast na rysunku 1.6 widać odpowiednie zmiany tablicy id. Graficzna reprezentacja struktury danych ułatwia zrozumienie działania algorytmu - pary wejściowe, które symbolizują połączone obiekty, są połączone w abstrakcyjnej reprezentacji. Podobnie jak poprzednio, należy na wstępie zauważyć, że połączenia w strukturze danych niekoniecznie pokrywają sic z połącze-

niami rzeczywistych obiektów określonymi przez pary

wcjściowe. Powodem jest to, iż są one konstruowane

przez algorytm w^r taki sposób, by ułatwić efektywne działanie operacji scalania i wyszukiwania.

Spójne składowe z rysunku 1.5 nazywa się drzewami; stanowią one fundamentalne struktury kombinato-ryczne, z którymi będziemy się spotykać przy licznych okazjach w całej książce. Szczegółowo własnościami drzew zajmiemy się w rozdziale 5. Z punktu widzenia

operacji scalania i wyszukiwania, drzewa z rysunku 1.5 są

przydatne, ponieważ można je szybko budować i mają taką własność, że dwa obiekty należą do tego samego

drzcw^fa wtedy i tylko wtedy, gdy są one połączone na w-e-

jściu. Przesuwając się w górę drzewa, możemy łatwo znaleźć jego korzeń. Mamy więc sposób, by szybko stwierdzić, czy dw^fa obiekty są połączone. Każde drzewo ma dokładnie jeden obiekt (a mianowicie korzeń), który wskazuje na siebie samego. Wskazanie na siebie samego nie zostało pokazane na rysunkach. Kiedy rozpoczniemy wędrówkę od dowolnego obiektu (węzła) drzewa, przeniesiemy się do obiektu, na który on wskazuje, by potem przejść do kolejnego obiektu, na który z kolei ten wskazu

je itd., zawrze na końcu dojdziemy do korzenia. Możemy to udowodnić przez indukcję: prawdą jest, żc zaraz po zainicjowaniu tablicy każdy jej element wskazuje na siebie

Rysunek 1.5

Reprezentacja szybkiego scalania za pomocą drzewa

samego, jak praw-dą jest i to, że o ile twierdzenie będzie

spełnione przed jakąś operacją scalania, to po tej operacji będzie również spełnione.

Diagramy z rysunku 1.4 dla algorytmu szybkiego wyszukiwania mająte same wdasności co te opisane w po-

przednich akapitach. Różnica między nimi polega na tym, że ze wszystkich węzłów drzewa szybkiego wyszukiwania

dochodzimy do korzenia od razu po przejściu jednego ^Ten rysunek przedstawia graficzną ,,    ,    ,,    r •    i    reprezentację przykładu z rysunku

czasem przejść przez kilka łączy.

łącza, a z węzłów drzewa szybkiego scalania potrzeba _{t 3} Rysuj_emy linie od obiektu i do

id[i}.

13