Drzewa stanowią podstawę wielu ważnych algorytmów. Te pożyteczne struktury danych pozwalają organizować informację w sposób umożliwiający zarówno szybkie do niej dotarcie (jak w przypadku tablic), jak i szybką modyfikację: usuwanie i dodawanie nowych danych (jak to ma miejsce w przypadku list). Nadają się one więc doskonale do reprezentowania zbiorów skończonych, które w zastosowaniach informatycznych powstają najczęściej przez dodawanie kolejnych elementów, usuwanie ich i sprawdzanie, czy dany element znajduje się w zbiorze (typowe operacje bazodanowe).
Drzewa są rozważane w teorii grafów jako niezorientowane grafy spójne bez cykli. Drzewa używane w informatyce będą miały jedną istotną różnicę: zawsze z drzewem będzie związany jeden wybrany wierzchołek, nazywany korzeniem. Typowy sposób reprezentowania drzew będzie polegał na ustaleniu dla każdego węzła dowiązania do jego sąsiadów znajdujących się dalej od korzenia. Korzeń drzewa jest punktem, przez który drzewo jest dostępne, a samą definicję drzewa podamy rekurencyjnie, tak aby w każdym węźle określić jego następników – tak jak w drzewie genealogicznym określa się dzieci każdego węzła. Zresztą terminologia drzewa genealogicznego przeniknęła do informatyki i mówimy o ojcach, synach, wnukach, stryjach, dziadkach, kuzynach, mając na myśli związki analogiczne do rodzinnych.
Jedyną istotną różnicą między listami a drzewami jest to, że każdy element listy ma co najwyżej jeden następnik, a węzeł drzewa (czyli odpowiednik elementu listy) może mieć ich kilka. Jeśli ma co najwyżej dwa, to takie drzewo nazwiemy binarnym i – jak się okaże umiejętność obsługi drzew binarnych łatwo przełoży się na drzewa ogólne.
Podobnie, jak z listami, zdefiniujemy drzewa o wartościach w zbiorze A rekurencyjnie, jako najmniejszy zbiór spełniający dwa warunki:
Zauważmy, że mówimy tu o ciągu drzew D – ważna jest dla nas kolejność. Czasami chcielibyśmy o tej kolejności zapomnieć i rozważać zbiór drzew zamiast ciągu – wtedy musimy odpowiednio zmodyfikować definicję.
Stopniem wierzchołka (węzła) nazwiemy liczbę jego synów. W szczególności, jeśli ciąg synów wierzchołka \(v\) jest pusty, to stopień \(v\) wynosi 0, a sam węzeł \(v\) nazwiemy liściem. Stopień drzewa, to maksimum ze stopni jego wierzchołków. Przyjmujemy, że stopień drzewa pustego, to \(-1\).
Ścieżką w drzewie nazwiemy ciąg \(v_0,\ldots,v_k\), gdzie dla każdego \(1\le j \le k\) węzeł \(v_j\) jest synem węzła \(v_{j-1}\). Długością takiej ścieżki jest \(k\). Ścieżka złożona z jednego węzła ma długość 0, ścieżka pusta ma długość \(-1\).
Poziom korzenia definiujemy, jako 0, zaś poziomem węzła nazwiemy długość ścieżki od korzenia do tego węzła. Wysokość drzewa, to poziom najgłębszego spośród węzłów (liści), czyli maksimum z poziomów wszystkich węzłów. Wysokość drzewa pustego, to \(-1\).
Drzewo binarne, to drzewo o stopniu nieprzekraczającym \(2\). Zacznijmy może od pokazania, jak można reprezentować takie drzewa.
type drzewo = ^węzeł; {drzewo binarne} węzeł=record w: typA; lsyn,psyn : drzewo; end;
Podobnie jak dla list, przyjmijmy do końca tego wykładu, że typA=Integer. Będziemy więc mieli do czynienia z drzewami liczb całkowitych.
Zauważmy, że od strony technicznej definicja drzewa (binarnego) różni się od definicji listy jedynie jednym polem więcej w rekordzie opisującym jego element, zwany tutaj węzłem – każdy węzeł ma 2 następniki, a nie jednego, jak to było w przypadku list. Zauważmy, że ponieważ znamy ograniczenie górne na liczbę synów, więc możemy statycznie zarezerwować dwa pola do reprezentowania wskaźników do nich. Zakładamy tu, że rozróżniamy prawego i lewego syna w tym sensie, że drzewo binarne może mieć obu synów, tylko prawego, tylko lewego i żadnego – wszystkie 4 przypadki dopuszczamy, jako możliwe.
Zacznijmy od funkcji, która sprawdza, czy w drzewie istnieje węzeł o wartości x.
function jest(d:drzewo; x:typA):Boolean; {przyjmuje wartość true wtedy i tylko wtedy, gdy w drzewie d znajduje się wartość x} begin if d=nil then jest :=false {puste drzewo nie zawiera żadnej wartości} else if d^.w = x then jest := true {a niepuste albo ma ją w korzeniu} else jest := jest (d^.lsyn,x) or jest (d^.psyn,x) {albo w lewym lub prawym synu} {do sprawnego wykonania ostatniego wiersza konieczne jest założenie o leniwym wyliczaniu} end;
Uwaga. W przedstawionej wersji jeśli nie ma leniwego wyliczania, to nawet w przypadku, gdy wartość x znajdziemy w lewym poddrzewie, będziemy dalej żmudnie szukali jej jeszcze w prawym, mimo że już i tak wynik funkcji jest wiadomy. Gdybyśmy nie mieli pewności co do leniwości, wtedy ostatni else powinno się skonstruować inaczej:
else if jest(d^.lsyn,x) then jest:= true else jest:=jest(d^.psyn,x)
Tym sposobem niejako wymuszamy leniwość wyliczania warunków logicznych.
Powyższa funkcja wyróżnia pewien porządek przejścia przez drzewo. Po upewnieniu się, że drzewo nie jest puste najpierw obsługujemy korzeń drzewa, potem jego lewe poddrzewo, a na końcu prawe. Nie jest to jedyna możliwa kolejność. Można sobie wyobrazić, że najpierw będziemy szukali x w lewym poddrzewie, potem dopiero w korzeniu, a potem w prawym. Albo wręcz najpierw w obu poddrzewach, a dopiero na końcu w korzeniu. Oczywiście każda z tych procedur ma swój odpowiednik w postaci procedury, która poddrzewa będzie badać w odwrotnej kolejności, czyli najpierw prawe, a potem lewe.
Wspomniane warianty przeszukiwania drzewa dotyczą trzech bardzo ważnych procedur, zwanych obiegami drzew. Sprawdźmy może, jak będzie wyglądać kolejność wypisywania węzłów następującego drzewa, w momencie, gdy zastosujemy zasygnalizowane wcześniej metody przechodzenia wszystkich elementów drzewa.
A
/ \
B C
/ \ / \
D E F G
/ \ \ \
H I J K
/ \ /
L M NOto wspomniane procedury:
Prefiksowa:
procedure wypiszPreLP(d:drzewo); begin if d<>nil then begin Write(d^.w); wypiszpreLP(d^.lsyn); wypiszpreLP(d^.psyn) end end;
Dla procedury wypiszPreLP porządek wypisywania węzłów naszego drzewa będzie następujący: ABDHILMECFJGKN
Infiksowa:
procedure> wypiszInfLP(d:drzewo); begin if d<>nil then begin wypiszInfLP(d^.lsyn); Write(d^.w); wypiszInfLP(d^.psyn) end end;
Dla procedury wypiszInfLP porządek wypisywania węzłów naszego drzewa będzie następujący: HDLIMBEAFJCGNK
Postfiksowa:
procedure wypiszPostLP(d:drzewo); begin if d<>nil then begin wypiszPostLP(d^.lsyn); wypiszPostLP(d^.psyn) Write(d^.w); end end;
Dla procedury wypiszPostLP porządek wypisywania węzłów naszego drzewa będzie następujący: HLMIDEBJFNKGCA
Dodajmy do tych trzech obiegów ich odpowiedniki wypiszPrePL, wypiszInfPL oraz wypiszPost różniące się od nich tylko tym, że najpierw wchodzą do prawego poddrzewa, a dopiero potem do lewego.
Zadanie: W jakiej kolejności wypiszą się węzły dla tych trzech procedur?
Rozwiązanie:
Czy widać jakieś związki z wynikami procedur LP? Ciąg powstały przez wywołanie wypiszInfPL jest po prostu odwróconym ciągiem powstałym przez wywołanie wypiszInfLP. Gdy przyjrzymy się dokładniej, zobaczymy że ciąg z wypiszPrePL jest odwróconym ciągiem z wypiszPostLP, a ciąg powstały z wywołania wypiszPostPL odwróconym ciągiem z wypiszPreLP.
Okazuje się, ze nie jest to przypadek. Dla ciągów powstałych z wywołania naszych procedur dla danego drzewa d wprowadźmy oznaczenia \(Pre_{LP}, Pre_{PL}, Inf_{LP}, Inf_{PL}, Post_{LP}\) i \(Post_{PL}\). Jeśli dodatkowo umówimy się, że dla słowa \(w\in A^*\) przez \(w^R\) oznaczamy jego odwrotność, czyli symbole czytane po kolei od tyłu, to zachodzi następujący lemat:
LEMAT
Dla każdych \(u,v\in A^*\) zachodzi \((uv)^R=v^Ru^R\).
DOWÓD
Oczywisty.
Możemy teraz sformułować następujące twierdzenie:
TWIERDZENIE O OBIEGACH
Dla każdego drzewa d, jeśli rozważane obiegi odwiedzają węzły w kolejności odpowiednio \(Pre_d{LP}, Pre_d{LP}, Inf_d{LP}, Inf_d{PL}, Post_d{LP} i Post_d{PL}\), to
DOWÓD
Indukcja ze względu na wielkość drzewa.
Baza: Jeśli drzewo jest puste, czyli d=nil, to wszystkie uzyskane słowa są puste, a więc równe sobie i swoim odwrotnościom.
Krok indukcyjny: Załóżmy, że d jest niepuste i ma n>0 węzłów. Wtedy ma na pewno korzeń \(r\) oraz dwa poddrzewa \(d_L\) i \(d_P\). Załóżmy, że dla wszystkich drzew o mniejszej niż n liczbie węzłów teza zachodzi. Pokażemy, że zachodzi również dla drzewa d.
Ponieważ drzewo d ma n węzłów, w tym korzeń, więc każde z jego poddrzew ma co najwyżej n-1 węzłów, zatem można do nich stosować założenie indukcyjne. Przeprowadźmy najpierw dowód tego, że \(Pre_d{LP}=Post_d{PL}^R\). Mamy zatem
\(Pre_d{LP}=r \cdot Pre_{d_L}{LP}\cdot Pre_{d_P}{LP}= r^R \cdot Post_{d_L}{PL}^R \cdot Post_{d_P}{PL}^R =\) \((Post_{d_P}{PL} \cdot Post_{d_L}{PL}\cdot r)^R = Post_d{PL}^R\).
Pierwsza z równości wynika z definicji obiegu prefiksowego LP, druga z równości wynika z założenia indukcyjnego, trzecia, to nasz lemat, a czwarta wynika z definicji obiegu postfiksowego PL.
Uzyskana równość kończy dowód pierwszego z podpunktów. Dowody pozostałych dwóch przebiegają analogicznie.
Zobaczmy teraz, jak można używać mechanizmu przekazywania parametrów procedury przy transferze informacji w drzewie. Rozwiążmy dwa zadania.
Zadanie 1. W każdym węźle v drzewa d zastąp wartość tego węzła przez sumę wartości wszystkich węzłów na ścieżce od d do v włącznie.
Rozwiązanie.
Jedyna trudność, to konieczność zadbania o to, żeby przy zmianie wartości węzłów uwzględniać to, że nie wolno tej samej wartości brać wiele razy pod uwagę. Narzuca się tu zatem porządek prefiksowy. Oto rozwiązanie:
procedure Nadsumuj(d:drzewo); procedure DodajGore(d:drzewo; k:Integer); {Dosumowuje wartość parametru k do węzła d i nową wartość przekazuje rekurencyjnie obu synom. Procedura wykonuje główna robotę; jedyną zmianą w stosunku do głównej procedury jest obecność dodatkowego parametru.} begin if' d<> nil then begin d^.w:=d^.w+k; DodajGore(d^.lsyn,d^.w); DodajGore(d^.psyn,d^.w); end; end; begin {Nadsumuj} DodajGore(d,0) end;
Zauważmy jedną bardzo ważną technikę. W naszym przypadku niezwykle uprościło całą procedurę wprowadzenie dodatkowego parametru informującego przetwarzany węzeł o tym, o ile zwiększyć się ma jego wartość. Często programiści niechlujnie programując dodają ten parametr do procedury zasadniczej, każąc użytkownikowi samemu zadbać o wywołanie jej z dodatkową wartością, zupełnie zbędną z punktu widzenia specyfikacji problemu – w naszym przypadku z zerem. Zapamiętajmy więc ważną zasadę:
Procedura powinna mieć tyle parametrów, ile jest to konieczne z punktu widzenia specyfikacji zadania. Wszelkie nadmiarowe parametry ułatwiające zaprogramowanie są wyrazem niechlujstwa. Również złą praktyką programistyczną jest nieumieszczanie istotnych parametrów w nagłówku i korzystanie ze zmiennych globalnych. Rekurencja i iteracja niezbyt się lubią nawzajem. Najczęściej dobrze jest zdecydować się na jedną z nich.
W Pascalu takie obudowanie zasadniczej procedury (w naszym przypadku DodajGore) właściwym interfejsem (w naszym przypadku Nadsumuj) jest naturalnie wpisane w koncepcję zagnieżdżania procedur. W językach rodziny C niestety procedur zagnieżdżać się nie da, co prowadzi do zmniejszenia czytelności kodu – ze struktury programu nie widać zależności funkcjonalnej między procedurami.
Wróćmy teraz do drugiego z naszych zadań.
Zadanie 2. W każdym węźle v drzewa d zastąp wartość tego węzła przez sumę wartości wszystkich węzłów w poddrzewie, którego v jest korzeniem.
Procedurę rozwiązującą zadania 2 nazwijmy Podsumuj.
procedure Podsumuj(d:drzewo); var dowol:Integer; {zaślepka – potrzebna tylko po to, żeby nie było błędu składniowego} procedure DodajDol(d:drzewo; var k:Integer); {Dosumowuje wszystkie wartości z poddrzewa pod znajdującego sie pod d do d^.w , a otrzymaną wartość przekazuje jako k węzłowi, który ja wywołał} var zdolu:Integer; begin if' d=nil then k:=0 {To przypisanie jest konieczne!} else begin DodajDol(d^.lsyn, zdolu); d^.w:=d^.w+zdolu; DodajDol(d^.psyn, zdolu); d^.w:=d^.w+zdolu; k:=d^.w end; end; begin {Podsumuj} DodajDol(d,dowol) {Można było uniknąć dowola wstawiając tu np. d^.w, ale to by zaciemniło kod} end;
Warto zapamiętać parę rad, które mogą nam ułatwić rozwiązywanie tego typu problemów.
W procedurach rekurencyjnych dotyczących drzew zawsze sprawdzamy na początku, czy argument nie jest nilem. Przy przekazywaniu informacji od korzenia w dół używamy najczęściej porządku prefiksowego, a informację przekazujmy przez wartość Przy przekazywaniu informacji z dołu drzewa do góry używamy najczęściej porządku postfiksowego i przekazujemy ją albo przez parametry wołane przez zmienną albo za pomocą funkcji.
Poznamy teraz technikę umożliwiającą rozwiązywanie całej klasy zadań i niezwykle wygodną. Nazwiemy ją techniką spaceru. Żeby zilustrować ją, a zarazem pokazać, czym się różni od standardowego przejścia rekurencyjnego, rozwiążmy jedno zadania na dwa sposoby. Zadanie polega na wyznaczeniu wysokości drzewa. Najpierw czysta rekurencja postfiksowa. Oczywiście postfiksowa, gdyż aby poznać wysokość drzewa, musimy w korzeniu znać wysokości jego synów, ci z kolei swoich – i tak dalej. Ewidentnie informacja wędruje z dołu.
function wysokość(d:drzewo):Integer; function max(a,b:Integer):Integer; begin if a<=b then max:=b else max:=a end {bez komentarza :-)} begin {wysokość} if d=nil then wysokość:=-1 else wysokość:=max(wysokość(d^.lsyn),wysokość(d^.psyn))+1 end;
I już! Wprost z definicji.
Teraz spacer. Technika spaceru polega na przejściu drzewa z stosownym porządku (tu akurat wybór porządku nie ma dużego znaczenia) i notowaniu na zmiennej globalnej zaobserwowanych informacji. U nas interesującą informacją będzie aktualna głębokość. Jeśli pobijemy rekord, to go zaktualizujemy.
function wysokośćSpacerowa(d:drzewo):Integer; var aktg,maxg:Integer; {aktualna i maksymalna głębokość} procedure spacer(d:drzewo); begin if d<>nil then begin {spacer} aktg:=aktg+1; {wywołano nas z poziomem o 1 za małym, więc ustawiamy go na naszą głębokość} if aktg>maxg then maxg:=aktg; spacer(d^.lsyn); spacer(d^.psyn); aktg:=aktg-1;{Nie wolno nam zapomnieć o tej instrukcji! Musimy ojcu odtworzyć jego głębokość.} end; {spacer} begin {WysokośćSpacerowa} aktg:=-1; maxg:=-1; spacer(d); WysokośćSpacerowa:=maxg <b>end</b>;
Tutaj sprawdzanie, czy rekord nie został pobity, mogliśmy przesunąć albo między wywołania dla synów (wtedy mielibyśmy coś w rodzaju obiegu infiksowego) albo po wywołaniu dla prawego syna (wtedy byłoby to postfiksowo) i ta wersja jest najefektywniejsza, ale zysk polega jedynie na tym, że rekordu nie ciułamy powiększając go o 1, tylko od razu – gdy będziemy w liściu aktualizujemy być może o kilka jednostek.
Zajmiemy się teraz drzewami ogólnymi. Zakładamy tu, że nic nie wiemy o stopniu poszczególnych węzłów. Najstosowniejszym pomysłem wydaje się więc zastosowanie list do implementacji synów węzłów. Gdy nie wiemy z góry, ilu synów ma który węzeł, listy wydają się być najlepszym rozwiązaniem. Każdy węzeł zatem będzie miał poza wartością dwa pola: wskaźnik do swojego skrajnie lewego syna oraz wskaźnik do prawego brata. Mamy więc następującą deklarację:
type DrzewoOgólne = ^WęzełOgólny; WęzełOgólny=record w: typA; lsyn,brat : drzewo; end;
Gdy przyjrzymy się tej definicji, zauważymy, że w zasadzie z punktu widzenia składni jest to identyczna definicja z definicją drzewa binarnego: jedyną różnicą jest inna nazwa drugiego pola wskaźnikowego, a co za tym idzie inna jego interpretacja. Zauważmy, że korzeń nie ma braci, zatem jego pole brat będzie zawsze wskazywało na nil. Przy okazji – często rozważa się inną strukturę danych – lasy, będące zbiorami drzew. Gdyby list zapoczątkowana przez pole brat korzenia była niepusta, uzyskalibyśmy naturalną metodę reprezentowania lasu.
Zobaczmy, jak zmieni się funkcja obliczająca wysokość drzewa ogólnego. Oto przykładowy kod:
function wysokosćOgólna(d:drzewo):Integer; function max(a,b:Integer):Integer; begin if a<=b then max:=a else max:=b end {bez komentarza :-)} begin {wysokość} if d= nil then wysokość:=-1 else wysokość:=max(wysokość(d^.lsyn)+1,wysokość(d^.brat)) end;
Różnica niewielka – dodawanie jedynki powinno dotyczyć tylko poziomów synów, a nie braci – stąd występuje ono tylko przy parametrze dotyczącym syna.
Dobrym ćwiczeniem jest zaprogramowanie zadań na drzewa binarne w wersji drzew ogólnych. Prawie wszystkie procedury wyglądają bardzo podobnie. Zauważmy, że o ile sensowne jest mówienie o porządku prefiksowym i postfiksowym (po prostu ojca przetwarzamy albo zanim przetworzymy synów, albo po nich), to porządek infiksowy nie jest taki oczywisty: nie wiadomo z góry po którym synu chcielibyśmy przetworzyć ojca.