Drzewa
Cechy drzew
Grafy skierowane wymagają do swej reprezentacji struktur danych, bardziej skomplikowanych niż listy, powiązanych systemem wskaźników. Węzły grafów są w tych strukturach reprezentowane przez rekordy, a krawędzie grafów są reprezentowane przez ich pola typu wskaźnikowego. Graf o specjalnych właściwościach taki, że:
podstruktury powiązane z jakimś węzłem nie są powiązane między sobą,
występuje węzeł zwany korzeniem,
z węzła korzenia, przez skończoną liczbę krawędzi można przejść do dowolnego węzła.
jest nazywany drzewem. Na rys 15.1 pokazano różne graficzne i tekstowe reprezentacje drzew.
Zarówno lista jak i drzewo są strukturami rekurencyjnymi. Lista może być:
listą pustą,
lub konkatenacją elementu podstawowego typu T i listy o typie podstawowym T,
Drzewo może być:
drzewem pustym,
węzłem ze skończoną liczbą dowiązanych struktur drzewiastych - poddrzew.
Z tego względu najwygodniej definiuje się dla drzewa operacje rekurencyjne.
Dla drzew obowiązują następujące zasady:
Każdy węzeł drzewa, z wyjątkiem węzła korzenia, ma jeden węzeł bezpośredniego poprzednika i może mieć kilka węzłów, będących jego bezpośrednimi następnikami. Węzły bezpośrednich następników są nazywane bezpośrednimi potomkami (ang. children). Węzeł bezpośredniego poprzednika jest nazywany bezpośrednim przodkiem (ang. parent, ancestor) węzła drzewa. Zbiór węzłów przodków jest zdefiniowany rekurencyjnie. Zawiera on bezpośredniego przodka i zbiór jego przodków, jeżeli bezpośredni przodek ma przodka. Zbiór następników węzła jest także zdefiniowany rekurencyjnie i zawiera bezpośrednie następniki węzła i zbiór ich następników.
Węzeł bez poprzedników jest nazywany korzeniem.
Węzeł bez następników jest nazywany liściem.
Węzły nie będące liśćmi są nazywane węzłami wewnętrznymi.
Liczba bezpośrednich potomków węzła wewnętrznego jest nazywana stopniem węzła. Maksymalny stopień wszystkich węzłów jest nazywany stopniem drzewa.
Liczba węzłów drzewa jest nazywana rozmiarem drzewa.
Scieżką w drzewie jest ciąg węzłów, które należy przejść od korzenia do węzła X.
Poszczególnym węzłom przypisuje się numer poziomu, nazywany też głębokością węzła. Liczba krawędzi, które trzeba przejść od korzenia do węzła X plus jeden (zakłada się, że do korzenia dochodzi jedna krawędź), lub alternatywnie liczba węzłów, przez które trzeba przejść, łącznie z węzłem X - jest długością drogi X, głębokością węzła X. Poziom korzenia drzewa jest równy jeden, poziomy innych węzłów są określone przez liczbę węzłów poprzedników plus jeden. Długość drogi do węzła na poziomie i jest równa i. Maksymalny poziom drzewa jest nazywany głębokością drzewa.
Dla węzła używa się też pojęcia wysokości. Wysokością węzła jest liczba krawędzi, które trzeba przejść od węzła X do najbardziej odległego węzła liścia w jego poddrzewie. Oznaczenia wysokości i głębokości węzłów drzewa pokazano na rys 15.2.
Długość drogi wewnętrznej drzewa jest równa sumie długości wszystkich dróg składowych. Średnia
długość drogi wewnętrznej w drzewie wynosi:
ni - liczba węzłów na poziomie i
h - liczba poziomów, n - liczba węzłów.
W pewnych operacjach na drzewach uwzględnia się także węzły, reprezentujące puste poddrzewa. W dalszym ciągu będą one nazywane węzłami zewnętrznymi. Węzły drzewa są na rysunkach reprezentowane przez koła, a krawędzie przez linie łączące. Puste poddrzewa (węzły zewnętrzne) mogą być jawnie reprezentowane przez inne symbole graficzne, np. kwadraty, dołączone do węzłów liści. Puste drzewo jest reprezentowane przez jeden kwadrat. Na rys. 15.2 pokazano drzewo z węzłami wewnętrznymi, liśćmi i węzłami zewnętrznymi.
d -
A
B
D
I
J
E
K
L
M
C
F
N
G
O
P
R
H
S
Rys. 15.1. Graficzne i tekstowe reprezentacje drzew: a - zbiory zagnieżdżone, b - nawiasy zagnieżdżone, c - graf, d - wcięcia
Rys. 15.2. Głębokości i wysokości węzłów w drzewie w notacji glębokość/wysokość.
Rys. 15. 3. Drzewo rozszerzone z węzłami pełnymi i pustymi
Długość drogi zewnętrznej jest sumą długości dróg do wszystkich węzłów zewnętrznych, reprezentujących puste poddrzewa. Przy jej obliczaniu, przy zakłada się, że każdy węzeł drzewa ma taką samą liczbę następników.
Jeżeli liczba węzłów, reprezentujących puste następniki na poziomie i wynosi mi , to średnia długość drogi zewnętrznej z wynosi:
gdzie: m liczba wszystkich węzłów pustych,
h - wysokość drzewa z poziomem węzłów pustych.
Długości dróg wewnętrznej i zewnętrznej wpływają na czas przeglądania drzewa. Od głębokości węzła zależy czas wyszukania węzła w drzewie.
Drzewo jest pełnym drzewem stopnia d, jeżeli każdy jego węzeł, (z wyjątkiem węzłów na poziomie głębokości drzewa, gdzie wszystkie węzły są liśćmi), ma d następników.
Maksymalna liczba węzłów w drzewie pełnym stopnia d, wynosi:
na poziomie 1 liczba węzłów 1
2 d
3 d2
itd. Łączna liczba węzłów w pełnym drzewie stopnia d o liczbie poziomów h:
dla d=2
N2(h)=2h-1
Drzewo o wartości d=2, jest nazywane drzewem dwójkowym - binarnym. Drzewo o wartości d=3 jest nazywane drzewem trójkowym, itd.
Drzewo jest kompletne - tj. pełne wtedy i tylko wtedy, gdy istnieje taka liczba q, że każdy węzeł zewnętrzny ma głębokość q lub q+1.
Drzewo jest zdegenerowane do postaci listy, jeżeli każdy jego węzeł ma dowiązany tylko jeden węzeł następnika, tzn. jeżeli dla każdego węzła co najwyżej jeden węzeł wewnętrzny jest jego potomkiem.
Implementacja drzewa w postaci struktur: statycznej i dynamicznej
Implementacja drzewa w postaci struktury dynamicznej wykorzystuje rekord węzła typu TWezelDrzewa, zawierający dane węzła oraz d pól łączników, wskazujących na rozłączne poddrzewa, dołączone do danego węzła. Wskaźnik na korzeń drzewa pozwala na dostęp do wszystkich elementów tej struktury.
CONST
d=...;
TYPE
PWezelDrzewa=^TWezelDrzewa;
TWezelDrzewa=RECORD
DaneWezla:TDane;
Nast :ARRAY[1..d] OF PWezelDrzewa;
END;
VAR korzen:PWezelDrzewa;
Rys. 15 4. Drzewo stopnia 3.
Wszystkie węzły drzewa mają taką samą strukturę, tj. posiadają zdefiniowaną liczbę łączników, bez względu na to, ile węzłów potomków jest do nich dołączone (rys. 15.4). Bardziej efektywna jest struktura drzewa wielokierunkowego, która pozwala na pominięcie przechowywania pustych następników, która będzie rozważana w dalszej części rozdziału.
W drzewie binarnym każdy węzeł posiada dwa następniki, wskazujące na prawe i lewe poddrzewo.
TYPE
PWezel2=^TWezel2;
TWezel2=RECORD
DaneWezla :TDane;
lewy,prawy:PWezel2;
END;
Drzewo binarne może być reprezentowane przez strukturę dynamiczną, złożoną z elementów typu TWezel2, lub przez tablicę o elementach typu danych węzła TDane. Jeżeli dane węzłów drzewa są przechowywane w tablicy, to przyjmuje się wówczas regułę, zachodzącą pomiędzy indeksami węzła i jego następników. Następnikom węzła o indeksie i odpowiadają indeksy 2*i - dla lewego następnika i 2*i+1 - dla prawego następnika. Węzły drzewa, przechowywanego w tablicy, nie zajmują dodatkowej pamięci na przechowywanie łączników do węzłów potomków, tak jak węzły przechowywane w strukturach dynamicznych. Jednak tablica musi mieć wymiar wymagany dla drzewa pełnego, o spodziewanej liczbie węzłów. Przy drzewie niezrównoważonym, część pamięci będzie zarezerwowana na węzły puste i nie będzie efektywnie wykorzystana.
Jedno z pól rekordu typu TDane, opisującego dane węzła, pełni w drzewach rolę klucza, wpływającego na sposób uporządkowania węzłów drzewa. Stosuje się dwa podstawowe sposoby uporządkowania drzewa, wykorzystujące relacje podane poniżej. Są one określone, przy założeniu, że węzły drzewa są przechowywane w tablicy rekordów a[1..n] i każdy węzeł a[i] zawiera pole klucz, według którego drzewo jest uporządkowane. Są nimi:
uporządkowanie wykorzystywane w drzewach binarnych, w których pomiędzy wartościami kluczy węzłów zachodzą relacje:
a[i].klucz > a[2*i].klucz,
a[i].klucz<= a[2*i+1].klucz, dla i=1..k, gdzie k=trunc(n/2),
a n jest liczbą wszystkich węzłów drzewa pełnego.
uporządkowanie wykorzystywane w stogach (kopcach BRT), w których pomiędzy wartościami kluczy węzłów zachodzą relacje:
a[i].klucz>=a[2*i].klucz,
a[i].klucz>=a[2*i+1].klucz, dla i=1..k, gdzie k=trunc(n/2),
przy założeniu, że stóg przechowuje maksymalną wartość klucza z drzewa,[B,k,paluszynski]
lub:
a[i].klucz<= a[2*i].klucz,
a[i].klucz<=a[2*i+1].klucz, dla i=1..k, gdzie k=trunc(n/2),
przy założeniu, że stóg przechowuje minimalną wartość klucza z drzewa [kingstone,Banach,R,K, Wirth, Bentley].
Ponadto stóg jest drzewem binarnym kompletnym, w którym na wszystkich poziomach, z wyjątkiem ostatniego, znajduje się pełna liczba węzłów. Ostatni poziom jest wypełniony od lewej pozostałą liczbą węzłów.
Drzewo dokładnie wyważone
W drzewie dokładnie wyważonym [ Wirth,Paluszyński], liczby węzłów dołączonych do lewego i prawego poddrzewa każdego węzła, różnią się co najwyżej o 1. Takie drzewo ma najmniejszą wysokość. Dla drzewa dokładnie wyważonego o N węzłach, w przybliżeniu wynosi ona log2N. Drzewa dokładnie wyważone umożliwiają więc szybkie wyszukiwanie.
Budowę drzewa dokładnie wyważonego, pokazuje rekurencyjna funkcja DW. Zwraca ona adres drzewa, które zostało utworzone z liczby węzłów, która jest parametrem funkcji. W każdym wywołaniu funkcji jest generowany nowy węzeł, do którego dane są wprowadzane za pomocą procedury Czytaj. W adresy jego lewego i prawego poddrzewa, są wstawiane adresy zwracane przez funkcję DW, wywołaną dwa razy: raz z liczbą węzłów, które należy umieścić w lewym i drugi raz z liczbą węzłów, które należy umieścić w prawym poddrzewie. Jeżeli przy kolejnym wywołaniu funkcji, liczba węzłów poddrzewa jest równa 0, jest zwracany adres równy NIL. Liczba węzłów lewego poddrzewa może być większa o 1, lub równa liczbie węzłów prawego poddrzewa.
FUNCTION DW(n:INTEGER):PWezel2;
VAR
b :PWezel2;
nl,np:INTEGER;
Dane :TDane;
BEGIN
IF n=0
THEN DW:=NIL
ELSE
BEGIN
nl:=n DIV 2;
np:=n-nl-1;
Czytaj(Dane);
NEW(b);
WITH b^ DO
BEGIN
DaneWezla :=Dane;
lewy:=DW(nl);
prawy:=DW(np);
DW:=b;
END
END
END; {DW}
Przed wywołaniem tej funkcji w programie, należy z klawiatury wprowadzić liczbę węzłów drzewa.
BEGIN
WRITE('Podaj liczbę węzłów drzewa');
READLN(n);
korzen:=DW(n);
END.
Drzewo wyważone, o minimalnej wysokości, utworzone za pomocą procedury DW, nie jest w żaden sposób uporządkowane. Aby było możliwe wyszukiwanie wzdłuż ścieżki, musiałoby być następnie doprowadzone do posortowanego drzewa binarnego lub stogu. Dzięki tworzeniu drzewa dokładnie wyważonego, skrócenie drogi poszukiwań może być średnio rzędu 39% (Wirth) w porównaniu z drzewem losowym. Opłacalność wyważania drzewa, zależy od współczynnika, zdefiniowanego jako: w/d,
gdzie d - częstość wstawiania,
w - częstość wyszukiwania.
Im w/d jest większe, tym balansowanie drzewa jest bardziej opłacalne. Opłacalność wyważania jest większa także, gdy liczba węzłów n jest duża.
Mniej ostrym kryterium wyważenia, od drzewa dokładnie wyważonego, jest drzewo wyważone. Drzewo jest wyważone, (zrównoważone), wtedy i tylko wtedy, gdy dla każdego węzła drzewa, wysokości dwóch jego poddrzew różnią się co najwyżej o 1. Od autorów tej definicji (Adelson -Velski i Landis), drzewa takie są nazywane drzewami AVL [Wirth, Paluszyński]. Wszystkie drzewa dokładnie wyważone, według poprzedniego kryterium, są też drzewami AVL, wyważonymi. Drzewo wyważone nie będzie wyższe od swojego odpowiednika - drzewa dokładnie wyważonego, o więcej niż 45% (Wirth). Wyważenie drzewa binarnego jest znacznie łatwiejsze, niż doprowadzenie go do dokładnego wyważenia. Odpowiednie algorytmy omówiono w [ wirth, paluszynski].
Binarne drzewa poszukiwań - drzewa BST
Drzewo jest uporządkowane, jeżeli jego gałęzie są uporządkowane. Uporządkowane drzewo binarne jest skończonym zbiorem elementów węzłów, z których każdy jest pusty, lub zawiera węzeł z dwoma rozłącznymi binarnymi drzewami: lewym i prawym poddrzewem. Elementy w drzewie są uporządkowane według pewnego klucza. Drzewa, w których dla wszystkich węzłów drzewa, klucze węzłów lewego poddrzewa są mniejsze, a wszystkie klucze węzłów prawego poddrzewa są większe od klucza węzła, jest nazywane binarnym drzewem poszukiwań (ang. Binary Search Tree - BST). Poszukiwanie węzła o określonym kluczu odbywa się wzdłuż ścieżki drzewa.
Jeżeli d jest stopniem drzewa, a h - jego wysokością, to w drzewie zrównoważonym o n węzłach:
dh =n
dla d=2 2h=n
oraz h log 2 =log n
stąd h= log n/log2;
h= log2n
Do znalezienia węzła w drzewie zrównoważonym o n węzłach, potrzeba więc, co najwyżej log2n.
Dołączanie węzła do drzewa
Procedura rekurencyjna Dolacz, dołączająca nowy węzeł do drzewa binarnego, reprezentowanego przez wskaźnik Korzen, zakłada, że drzewo ma zostać uporządkowane według pola klucz, znajdującego się w rekordzie danych węzła typu TDane. Procedura znajduje koniec ścieżki, do której zostanie dołączony nowy element, przechodząc od węzła korzenia, do węzła liścia, lub węzła z jednym potomkiem. Jako następny węzeł na ścieżce jest wybierany węzeł lewy, jeżeli wartość klucza w węźle dołączanym jest mniejsza od wartości klucza w węźle badanym, lub węzeł prawy w przeciwnym przypadku. Po znalezieniu końca ścieżki, tzn. gdy adres kolejnego węzła na ścieżce jest równy NIL, jest generowany nowy węzeł, którego adres jest wstawiany w miejsce przekazane jako parametr procedury. Do nowego węzła są wstawiane dane, stanowiące parametr procedury oraz jego obydwa następniki prawy i lewy są ustawiane na NIL. Ponadto w zmiennej globalnej lw, procedura liczy liczbę węzłów, dołączonych do drzewa.
PROCEDURE Dolacz(b:PWezel2; Dane:TDane);
BEGIN
IF b=NIL
THEN
BEGIN
NEW(b);
b^.lewy:=NIL;
b^.prawy:=NIL;
b^.DaneWezla:=Dane;
lw:=lw+1
END
ELSE
IF dane.klucz<b^.DaneWezla.klucz
THEN Dolacz(b^.lewy,Dane)
ELSE Dolacz(b^.prawy,Dane)
END; {Dolacz}
W celu dołączenia kolejnych węzłów do drzewa, procedurę Dolacz, wywołuje się w pętli. Jej wywołanie musi zostać poprzedzone wprowadzeniem danych wstawianych do węzła. Wprowadzenie danych wykonuje za pomocą procedura Czytaj. Blok wywołujący procedurę Dolacz, korzysta z poniższych deklaracji:
VAR
Korzen:PWezel2;
dane :TDane;
BEGIN
Korzen:=NIL;
REPEAT
Czytaj(dane);
Dolacz(Korzen,dane)
UNTIL koniec;
END.
Od wartości pola klucz rekordu dane, zależy wybór ścieżki w drzewie. Przy założeniu, że kluczem jest wartość całkowita, ciąg liczb: 5, 6, 2, 8, 1, 7, 4, 3, 12, utworzy drzewo z rys. 15.5.
Rys. 15. 5. Drzewo binarne określonego ciągu.
Zapis drzewa z rysunku 15.5 w postaci tablicy:
Numer elementu |
Wartość klucza |
1 |
5 |
2 |
2 |
3 |
6 |
4 |
1 |
5 |
4 |
6 |
- |
7 |
8 |
8 |
- |
9 |
- |
10 |
3 |
11 |
- |
12 |
- |
13 |
- |
14 |
7 |
15 |
12 |
Na kształt drzewa, utworzonego z ciągu kluczy, ma wpływ wartość klucza pierwszego elementu wstawianego do korzenia drzewa oraz kolejność wprowadzania danych. Zamiana kolejności dwóch pierwszych elementów ciągu, którego drzewo pokazano na rys. 15.5, a tym samym wartości klucza wstawianego do korzenia, powoduje powstanie drzewa z rys. 15.6.
Binarne drzewo poszukiwań, w którym dla każdego węzła, klucze w lewym poddrzewie są mniejsze od kluczy w prawym poddrzewie nie są uporządkowane poziomami, tzn. w ścieżce prowadzącej od korzenia do określonego węzła, wartości nie są uporządkowane rosnąco. Jednak przy odpowiednim przeglądaniu drzewa, przy odczycie można otrzymać ciąg kluczy rosnący lub malejący. Takie sortowanie danych, przez utworzenie drzewa binarnego i odpowiednie odczytanie danych z drzewa jest stabilne, tzn. elementy o tej samej wartości, będą miały taką samą kolejność jak przed sortowaniem.
Rys. 15.6. Drzewo binarne po zmianie kolejności dwóch pierwszych elementów ciągu.
Jeżeli przy wstawianiu, w korzeniu są umieszczone dane z nieodpowiednią wartością klucza, drzewo ulegnie zdegenerowaniu. W skrajnym przypadku, np. gdy wartości wstawiane do drzewa są uprządkowane rosnąco lub malejąco, zostanie utworzona lista. W tym przypadku średnia liczba porównań, przy wyszukiwaniu elementu, jest równa n/2, dla n węzłów w drzewie. Szybkość wyszukiwania w drzewie zależy więc silnie, od stopnia zrównoważenia drzewa, którego miarą jest wysokość drzewa.
Operację dołączania do drzewa można także zapisać iteracyjnie. Ten algorytm, realizowany przez zamieszczoną poniżej procedurę DolaczI, jest to jednak bardziej skomplikowany od algorytmu rekurencyjnego i wymaga zdefiniowania pomocniczej funkcji SzukajPI i procedury Wstaw. Funkcja SzukajPI znajduje węzeł, zawierający poszukiwany klucz, lub węzeł, znajdujący się na końcu ścieżki - (węzeł przodka), do którego węzeł z poszukiwanym kluczem powinien zostać dołączony.
FUNCTION SzukajPI(klucz:TKlucza; b:PWezel2):PWezel2;
VAR
y:PWezel2;
BEGIN
y:=NIL;
WHILE (b<>NIL) AND (klucz<>b^.DaneWezla.klucz) DO
BEGIN
y:=b;
IF klucz<b^.DaneWezla.klucz
THEN b:=b^.lewy
ELSE b:=b^.prawy
END;
IF b=NIL
THEN SzukajPI:=y
ELSE SzukajPI:=b
END; {SzukajPI}
Do utworzenia nowego węzła wykorzystuje się procedurę Wstaw, generującą i wypełniającą nowy węzeł.
PROCEDURE Wstaw(Dane:TDane; b:PWezel2);
BEGIN
NEW(b);
b^.lewy:=NIL;
b^.prawy:=NIL
b^.DaneWezla:=Dane;
END; {Wstaw}
Procedura DolaczI wyszukuje węzeł z podanym kluczem, lub węzeł do którego nowy węzeł z podanym kluczem ma zostać dołączony, za pomocą funkcji SzukajPI. Wskaźnik do znalezionego węzła, zostaje zapamiętany w pomocniczej zmiennej wskaźnikowej p. Jeśli znaleziony węzeł zawiera poszukiwany klucz, jest wyprowadzany komunikat o znalezieniu klucza w drzewie. W przeciwnym przypadku należy sprawdzić, czy nowy węzeł ma być dołączony jako lewy, czy jako prawy następnik znalezionego węzła, znajdującego się na końcu wybranej ścieżki i dołączyć go w odpowiednie miejsce, za pomocą procedury Wstaw.
PROCEDURE DolaczI(q:PWezel2; Dane:TDane);
VAR p:PWezel2;
BEGIN
p:=SzukajPI(Dane.klucz,q);
IF p<>NIL
THEN
IF Dane.klucz=p.DaneWezla.klucz
THEN WRITELN('Znaleziono klucz ', Dane.klucz)
ELSE
IF Dane.klucz<p^.DaneWezla.klucz
THEN Wstaw(Dane,p^.lewy)
ELSE Wstaw(Dane,p^.prawy);
END; {DolaczI}
Procedura DolaczI może być używana do tworzenia drzewa, w celu posortowania danych. Aby sortowanie było stabilne, tj. by rekordy o takiej samej wartości klucza, w strukturze posortowanej znajdowały się względem siebie w takiej samej kolejności, w jakiej były wprowadzane, warunek gdy klucze są równe:
Dane.klucz=p^.DaneWezla.klucz
powinien być potraktowany tak samo jak warunek, gdy wartość klucza danych wstawianych jest większa od danych badanego węzła:
Dane.klucz>p^.DaneWezla.klucz,
tak, jak to wykonuje procedura DolaczI, w której warunkiem przejścia do lewego potomka jest spełnienie relacji <, a do prawego relacji >=.
Wyszukiwanie w drzewie binarnym
Tę samą regułę, której używa się przy wstawianiu nowego węzła, do binarnego drzewa poszukiwań, stosuje się także przy wyszukiwaniu. Rekurencyjne wyszukiwanie węzła, o podanym kluczu, realizuje funkcja SzukajR:.
FUNCTION SzukajR(klucz:TKlucza; b:PWezel2):PWezel2;
BEGIN
IF (b=NIL) OR (b^.DaneWezla.klucz=klucz)
THEN SzukajR:=b
ELSE
IF klucz<b^.DaneWezla.klucz
THEN SzukajR:=SzukajR(klucz,b^.lewy)
ELSE SzukajR:=SzukajR(klucz,b^.prawy)
END; {SzukajR}
Wywołanie funkcji SzukajR, pokazane poniżej, musi być poprzedzone wczytaniem poszukiwanego klucza. Jeżeli węzeł zostanie znaleziony, jego dane są wyprowadzane na ekran za pomocą procedury Wyswietl. W przeciwnym przypadku jest wyprowadzany odpowiedni komunikat.
READ(KluczPoszukiwany)
p:=SzukajR(KluczPoszukiwany,Korzen)
IF p=NIL
THEN WRITELN('Nie znaleziono wezla z poszukiwanym kluczem')
ELSE Wyswietl(p^.DaneWezla);
Iteracyjna funkcja SzukajI, wyszukiwania węzła zawierającego podany klucz jest pokazana poniżej. Przegląda ona węzły drzewa, przechodząc w ścieżce do lewego lub prawego potomka węzła, w zależności od relacji, zachodzącej pomiędzy kluczem poszukiwanym, a kluczem węzła odwiedzanego. Osiągnięcie adresu równego wartości NIL oznacza, że w drzewie nie znaleziono węzła z poszukiwaną wartością klucza.
FUNCTION SzukajI(klucz:TKlucza; b:PWezel2):PWezel2;
BEGIN
WHILE (b<>NIL) AND (klucz<>b^.DaneWezla.klucz) DO
IF klucz<b^.DaneWezla.klucz
THEN b:=b^.lewy
ELSE b:=b^.prawy;
SzukajI:=b;
END; {SzukajI}
Funkcję SzukajI wywołuje się z podaniem, wprowadzonej wcześniej, wartości klucza poszukiwanego i adresu korzenia drzewa.
p:=SzukajI(KluczPoszukiwany,Korzen);
Jeżeli do węzłów liści dowiąże się węzeł wartownika, jak pokazuje rys. 15.7, i wpisze się do jego klucza wartość klucza poszukiwanego (na rysunku wartość 9), to do wykrycia wyjścia z pętli WHILE wystarczy sprawdzać jeden warunek, ponieważ węzeł z poszukiwanym kluczem zawsze zostanie znaleziony.
Rys. 15. 7 Drzewo binarne z węzłem wartownika
Deklaracja węzła wartownika musi być umieszczona w programie głównym:
VAR W:PWezel2;
Funkcja SzukajWI wykorzystuje globalny wskaźnik do węzła wartownika W.
FUNCTION SzukajWI(klucz:TKlucza; b:PWezel2):PWezel2;
BEGIN
W^.DaneWezla.klucz:=klucz;
WHILE klucz<>b^.DaneWezla.klucz DO
IF klucz<b^.DaneWezla.klucz
THEN b:=b^.lewy
ELSE b:=b^.prawy;
IF b=W
THEN SzukajWI:=NIL
ELSE SzukajWI:=b;
END; {SzukajWI}
W tym przypadku liczba wykonywanych porównań zmniejsza się o 1/3.
Również wyszukiwanie rekurencyjne jest bardziej efektywne przy zastosowaniu wartownika:
FUNCTION SzukajWR(klucz:TKlucza; b:PWezel2):PWezel2;
BEGIN
IF b^.DaneWezla.klucz=klucz
THEN SzukajWR:=b
ELSE
IF klucz<b^.DaneWezla.klucz
THEN SzukajWR:=SzukajWR(klucz,b^.lewy)
ELSE SzukajWR:=SzukajWR(klucz,b^.prawy)
END; {SzukajWR}
W celu zapamiętania wskaźnika, do węzła znalezionego, jest wymagana deklaracja pomocniczej zmiennej wskaźnikowej p:
VAR p:PWezel2;
Przed wywołaniem funkcji SzukajWR, należy wczytać z klawiatury poszukiwany klucz KluczPoszukiwany i wpisać go do węzła wartownika. Znalezienie poszukiwanego klucza w węźle wartownika oznacza, że drzewo nie zawiera węzła z poszukiwanym kluczem. Jeżeli węzeł poszukiwany zostanie znaleziony, jego dane wyświetla procedura Wyświetl.
READ(KluczPoszukiwany)
W^.DaneWezla.klucz:=KluczPoszukiwany;
p:=SzukajWR(KluczPoszukiwany,Korzen)
IF p=W
THEN WRITELN('Nie znaleziono wezla z poszukiwanym kluczem')
ELSE Wyswietl(p^.DaneWezla);
Podczas wyszukiwania w drzewie z wartownikiem, liczba porównań sprawdzających, czy węzeł zawiera poszukiwany klucz, zmniejsza się o połowę. W zastosowaniach, wymagających częstego przeszukiwania i sortowania ten algorytm jest efektywny.
Przeglądanie drzewa
Dla trzech węzłów może być sześć kolejności przeglądania. Przy założeniu, że węzeł lewy jest przeglądany przed węzłem prawym, sprowadza się to do trzech kolejności, pokazanych na rys. 15.8:
pre order - przeglądanie wzdłużne (a),
in order - przeglądanie poprzeczne (b),
post order - przeglądanie wsteczne (c).
Rys. 15.8. Przeglądanie drzewa - a - wzdłużne, b - poprzeczne, c - wsteczne
Tym sposobom przeglądania odpowiadają procedury Pre, In, Post. Różnią się one kolejnością wykonywania operacji, realizowanej przez procedurę P, na przeglądanym węźle b oraz wywołań rekurencyjnych.
Parametry procedur rekurencyjnych są przekazywane przez wartość. Procedury odwiedzają węzły wewnętrzne i zewnętrzne. Dotarcie do węzła zewnętrznego kończy ciąg wywołań rekurencyjnych na tej ścieżce.
Procedura Pre, realizująca przeglądanie wzdłużne, wykonuje operację P na węźle odwiedzanym b, a następnie przegląda jego lewe, a potem prawe poddrzewo. Kolejność odwiedzanych węzłów, dla przykładowego drzewa, przy zastosowaniu różnych sposobów przeglądania drzewa jest pokazana na rys. 15.9.
Rys 15.9. Numeracja węzłów drzewa, w kolejności odwiedzania węzłów przy przeglądaniu
a) pre order
b) in order
c) post order
PROCEDURE Pre(b:PWezel2);
BEGIN
IF b<>NIL
THEN
BEGIN
P(b);
Pre(b^.lewy);
Pre(b^.prawy);
END
END; {Pre}
Procedura In, realizująca przeglądanie poprzeczne, odwiedza najpierw lewe poddrzewo węzła. Po kolejnych wywołaniach rekurencyjnych, dociera w ten sposób do lewego pustego węzła, skrajnego lewego węzła liścia drzewa, a następnie cofa się do węzła przodka. Po powrocie z lewego poddrzewa do węzła przodka, wykonuje operację P na węźle odwiedzanym b. Następnie przegląda jego prawe poddrzewo. Po powrocie z prawego poddrzewa, wraca na wyższy poziom.
PROCEDURE In(b:PWezel2);
BEGIN
IF b<>NIL
THEN
BEGIN
In(b^.lewy);
P(b);
In(b^.prawy);
END
END; {In}
Procedura Post, realizująca przeglądanie wsteczne, odwiedza najpierw lewe poddrzewo węzła. Doprowadza to także do dotarcia do lewego pustego węzła, skrajnego lewego węzła liścia drzewa. Następnie cofa się do węzła przodka i przegląda jego prawe poddrzewo. Dopiero przy drugim powrocie do węzła przodka, wykonuje operację P na węźle odwiedzanym b, po której wraca na wyższy poziom.
PROCEDURE Post(b:PWezel2);
BEGIN
IF b<>NIL
THEN
BEGIN
Post(b^.lewy);
Post(b^.prawy);
P(b);
END
END; {Post}
Wywoływana w tych procedurach procedura P wykonuje jakąś operacje na węźle b. Może na przykład zliczać węzły i wpisywać do węzła, w pole Numer w rekordzie DaneWezla - jego numer. Zmienna, reprezentująca bieżący numer węzła, musi być zmienną globalną, np. i, lub musi być przekazywana jako parametr. Operacje procedury P:
i:=i+1;
b^.DaneWezła.Numer:=i;
Stosowanie różnych kolejności wykonywania tej samej operacji na węźle, może prowadzić do zupełnie innych wyników. Na przykład spowodować różne ponumerowanie węzłów, przy innych kolejnościach przeglądania. Różne kolejności odwiedzania węzłów są przydatne do różnych celów.
Przeglądanie poprzeczne - in order stosuje się np. w poniższej procedurze WyprowadzR, przy wyświetlaniu danych z węzłów drzewa, w kolejności wzrastających wartości kluczy:
PROCEDURE WyprowadzR(b:PWezel2);
BEGIN
IF b<>NIL
THEN
BEGIN
WyprowadzR(b^.lewy);
Wyswietl(b^.DaneWezla);
WyprowadzR(b^.prawy);
END
END; {WyprowadzR}
Taką samą kolejność przeglądania drzewa stosuje procedura Wyświetl_Drzewo z zadania zad49.txt . Wyprowadza ona na ekran dane z rekordów drzewa, (za pomocą procedury Wyswietl), z podaniem numeru poziomu węzła.. Numer poziomu węzła jest przekazywany do procedury jako parametr i , przekazywany przez zmienną. W procedurach z zadania zad49.txt wykorzystuje się typ węzła i typ wskaźnikowy, których deklarację zamieszczono poniżej. Poziom węzła wpływa na czas wyszukiwania węzła.
TYPE
Wsk=^Wezel;
Wezel=RECORD
danew :TDane;
lewy,prawy:Wsk;
END;
Typ Wsk jest typem wskaźnikowym, wskazującym na rekord węzła, w którym znajduje się pole danew typu rekordowego, zawierającego dane węzła. Są one wyprowadzane na ekran za pomocą procedury Wyswietl.
PROCEDURE WyswietlDrzewo(wb:Wsk; VAR i:INTEGER);
BEGIN
IF wb<>NIL
THEN
BEGIN
i:=i+1;
WyswietlDrzewo(wb^.lewy,i);
WRITELN('---------------------------------');
WRITELN('Poziom wezla ',i);
Wyswietl(wb^.danew);
lw:=lw+1;
WyswietlDrzewo(wb^.prawy,i);
i:=i-1
END
END; {WyswietlDrzewo}
Przeglądanie wzdłużne - pre order, stosuje się przy zapisie drzewa do pliku. Stosuje je procedura Skladuj_Drzewo z zadania zad49.txt. Plik składa się z elementów zawierających wyłącznie dane węzła.
PROCEDURE Skladuj_Drzewo(wb:Wsk);
BEGIN
IF wb<>NIL
THEN
BEGIN
WRITE(plik,wb^.danew);
Skladuj_Drzewo(wb^.lewy);
Skladuj_Drzewo(wb^.prawy)
END
END; {Skladuj_Drzewo}
Plik, w którym składuje się dane z drzewa, musi być zadeklarowany jako globalny w stosunku do rekurencyjnej procedury Skladuj_Drzewo. Musi on zostać przydzielony i przygotowany do zapisu, przed jej wywołaniem. Składowanie w kolejności pre order, zapewnia utworzenie takiego samego drzewa przez iteracyjną procedurę Odtworz_Drzewo, przy odzyskiwaniu drzewa na podstawie danych z pliku. Kolejne węzły, których dane zostały odczytane z pliku są tworzone i dołączane przez procedurę Dolacz.
Składowanie drzewa przy zastosowaniu innej kolejności przeglądania, np. in order, po odtworzeniu drzewa na podstawie pliku, doprowadziłoby do utworzenia drzewa, zdegenerowanego do postaci listy.
Procedura odtwarzająca drzewo na podstawie pliku jest zapisana przy użyciu iteracji, która wydaje się bardziej naturalna dla sekwencyjnego odczytu danych z pliku.
PROCEDURE Odtworz_Drzewo(wb:Wsk);
VAR
dane:TDane;
plik:FILE OF TDane;
lw :INTEGER;
BEGIN
{$I-}
RESET(plik);
{$I+}
IF IORESULT<>0
THEN WRITELN('Nie znaleziono pliku')
ELSE
BEGIN
lw:=0;
WHILE NOT EOF(plik) DO
BEGIN
READ(plik,dane);
Dolacz(korzen,dane)
END
END
END; {Odtworz_Drzewo}
Przeglądanie pre order zastosowano do liczenia węzłów liści w drzewie w procedurze Licz_Lisc z zad49.txt. Liście są liczone w zmiennej globalnej ll. Procedura odwiedza tylko węzły wewnętrzne. Zastosowanie innego algorytmu przeglądania do tego celu, dałoby także dobre i takie same wyniki.
PROCEDURE Licz_Lisc(wb:Wsk);
BEGIN
IF (wb^.lewy=NIL) AND (wb^.prawy=NIL)
THEN ll:=ll+1
ELSE
BEGIN
IF wb^.lewy<>NIL
THEN Licz_Lisc(wb^.lewy);
IF wb^.prawy<>NIL
THEN Licz_Lisc(wb^.prawy)
END
END; {Licz_Lisc}
Liczba liści jest pewną miarą zrównoważenia drzewa. Drzewo zdegenerowane ma jeden liść. Drzewo pełne ma llp=trunc(n/2)+1 liści. Im liczba liści jest bardziej zbliżona do llp, tym drzewo jest bardziej zrównoważone
Przeglądanie pre order zastosowano także do liczenia węzłów w drzewie w procedurze Licz_Wezly, oraz do liczenia wysokości drzewa w procedurze Max_Dlug_Sciezki z zad49.txt. Węzły są zliczane w zmiennej globalnej lw. Procedura Licz_Wezly odwiedza węzły wewnętrzne i zewnętrzne, przy czym dla węzła zewnętrznego kończy wywołania rekurencyjne.
PROCEDURE Licz_Wezly(wb:Wsk);
BEGIN
IF wb<> NIL
THEN
BEGIN
lw:=lw+1;
Licz_Wezly(wb^.lewy);
Licz_Wezly(wb^.prawy);
END
END; {Licz_Wezly}
Podczas wyznaczania maksymalnej długości ścieżki, wartość zmiennej i, przechowującejdługość ścieżki dla węzła wewnętrznego, zwiększa się przed wywołaniem rekurencyjnym i zmniejsza po powrocie z rekurencji. Po zwiększeniu, aktualna długość ścieżki jest porównywana z dotychczasową maksymalną i ewentualnie zostaje ustalona nowa wartość maksymalna. Aktualna długość ścieżki i oraz dotychczasowa maksymalna długość max są przekazywane jako parametry. Ich początkowe wartości muszą zostać ustalone przed wywołaniem procedury. Procedura odwiedza węzły wewnętrzne i zewnętrzne. Maksymalna długość ścieżki określa wysokość drzewa, a tym samym maksymalny czas znalezienia węzła w drzewie.
PROCEDURE Max_Dlug_Sciezki(VAR max,i:INTEGER;wb:Wsk);
BEGIN
IF wb<>NIL
THEN
BEGIN
i:=i+1;
IF i>max
THEN max:=i;
Max_Dlug_Sciezki(max,i,wb^.lewy);
Max_Dlug_Sciezki(max,i,wb^.prawy);
i:=i-1
END
END; {Max_Dlug_Sciezki}
Początkowe wartości zmiennych globalnych, wykorzystywanych w procedurach, muszą zostać ustalone przed wywołaniem procedur w programie lub procedurze nadrzędnej. W procedurach Licz_Lisc, Licz_Wezly i Max_Dlug_Sciezki zmiana algorytmu przeglądania na inny nie wpływa na wynik obliczeń.
Drzewo może być zastosowane do zapisu wyrażeń arytmetycznych. Drzewo wyrażenia:
(a+b/c)*(d-e*f)
pokazano na rys 15.10.
Przeglądanie drzewa wg. różnych algorytmów, daje inne notacje zapisu wyrażenia arytmetycznego, o różnej kolejności zapisu argumentów i operatorów:
notację wrostkową (in order) (a+b/c)*(d-e*f),
prefiksową (pre order) *,+a,/,b,c,-d,*e,f,
postfiksową (post order)[Wroblewski] a,b,c,/,+,d,e,f,*,-,*.
W powszechnie używanej notacji wrostkowej, argumenty są rozdzielane operatorami. Dla określenia kolejności wykonywania operacji innej niż wynika to z priorytetów operatorów, używa się nawiasów okrągłych. W notacji prefiksowej operatory poprzedzają argumenty, w notacji postfiksowej beznawiasowej, nazywanej Odwrotną Notacją Polską, operatory zapisuje się za argumentami. Przeglądanie drzewa w kolejności post order daje zapis wyrażenia w Odwrotnej Notacji Polskiej - ONP, np.: a,b,c,/,+,d,e,f,*,-,*.
Rys. 15. 10. Drzewo wyrażenia arytmetycznego (a+b/c)*(d-e*f)
Notacja ONP została wynaleziona przez polskiego matematyka, zajmującego się logiką, prof. Łukasiewicza (1878-1956) i jest stosowana do analizy wyrażeń arytmetycznych w translatorach.
Argumenty wyrażenia czyta się przeglądając drzewo w kolejności post order, odkładając je kolejno na stosie. Po przeczytaniu operatora, ze stosu ściąga się odpowiednią do operatora liczbę argumentów i wykonuje się operację, po czym jej wynik znowu jest odkładany na stos jako kolejny argument.
Stan stosu dla wyrażenia z rysunku 15.10, przed odczytem kolejnych operatorów i po wykonaniu operacji (szczyt stosu z prawej, elementy stosu rozdzielone przecinkami, wynik wykonanej operacja jest zapisany w notacji zwykłej jako element stosu), zmienia się w następujący sposób:
1. a,b,c
2. a,b/c
3. a+b/c
4. a+b/c,d,e,f
5. a+b/c,d,e*f
6. a+b/c,d-e*f
7. (a+b/c)*(d-e*f)
8. stos pusty
Usuwanie węzła z drzewa.
Stopień skomplikowania operacji usuwania węzła z drzewa, zależy od jego położenia w drzewie. Jeżeli usuwanym węzłem jest węzeł liścia, np. węzeł o wartości klucza=60 na rys. 15.11, wystarczy wyzerować odpowiedni następnik w węźle ojca, co pokazuje rys. 15.12.
Rys. 15.11 Drzewo binarne przed usunięciem węzłów
Rys.15. 12. Drzewo binarne - po usunięciu węzła liścia o wartości klucza 60
Jeżeli usuwanym węzłem jest węzeł posiadający jednego potomka, np. węzeł o kluczu=50 na rys. 15.11, wówczas potomek węzła usuwanego, staje się bezpośrednim potomkiem węzła ojca usuwanego węzła, co pokazuje rys. 15.13.
Rys. 15.13. Drzewo binarne z rys. 15.11, po usunięciu węzła z jednym potomkiem, o wartości klucza 50
Jeżeli węzeł usuwany ma dwóch bezpośrednich potomków, trzeba go zastąpić potomkiem w porządku. W tym celu można zastosować jeden z trzech algorytmów.
Algorytm 1: Dane węzła usuwanego zostają zastąpione danymi węzła, będącego potomkiem w porządku. Takim potomkiem będzie skrajnie prawy węzeł lewego poddrzewa, posiadający wartość klucza równą maksymalnej wartości klucza z lewego poddrzewa, lub skrajnie lewy węzeł prawego poddrzewa, o wartości klucza równej minimalnej wartości prawego poddrzewa węzła usuwanego.
Algorytm może więc być realizowany w dwóch wersjach. Na rysunku 15.14, węzeł o wartości 200 został zastąpiony potomkiem w porządku, o wartości klucza 160, znajdującym się na końcu prawej ścieżki lewego poddrzewa.
Rys. 15.14. Drzewo binarne z rys. 15.11, po usunięciu węzła o wartości klucza 200, z dwoma potomkami.
Algorytm 1 wersja 1
Rys. 15.15. Drzewo binarne z rys. 15.11, po usunięciu węzła o wartości klucza 200, z dwoma potomkami.
Algorytm 1 wersja 2.
Na rysunku 15.15, węzeł o wartości 200 został zastąpiony potomkiem w porządku, o wartości klucza 210, znajdującym się na końcu lewej ścieżki prawego poddrzewa.
Algorytm 2: Do węzła ojca, węzła usuwanego należy dołączyć prawe poddrzewo węzła usuwanego. Lewe poddrzewo węzła usuwanego należy dołączyć na końcu lewej ścieżki, prawego poddrzewa, tzn. do węzła prawego poddrzewa węzła usuwanego, zawierającego minimalną wartość w tym poddrzewie. Pokazano to na rysunku 15.16.
Rys. 15.16. Drzewo binarne z rys 15.11, po usunięciu węzła o wartości klucza 200, z dwoma potomkami. Algorytm 2.
Algorytm 3: Do węzła ojca węzła usuwanego należy dołączyć lewe poddrzewo, węzła usuwanego. Prawe poddrzewo, węzła usuwanego należy dołączyć na końcu prawej ścieżki lewego poddrzewa, tzn. do węzła lewego poddrzewa węzła usuwanego, zawierającego maksymalną wartość w tym poddrzewie. Pokazano to na rys. 15.17.
Rys. 15.17. Drzewo binarne z rys. 15.11, po usunięciu węzła o wartości klucza 200, z dwoma potomkami. Algorytm 3.
W zadaniu zad49.txt do usuwania węzła, zawierającego dane osoby o podanym nazwisku nazwp, w procedurze Skresl zaimplementowano algorytm 3. Pierwszym krokiem algorytmu jest znalezienie węzła, zawierającego podane dane. Szukając węzła usuwanego ebz, należy także znaleźć węzeł jego ojca epz. Przeglądanie drzewa zaczyna się od korzenia przekazanego do procedury Szuk_Pop, jako parametr eb. Procedura Szuk_Pop sprawdza klucze w węzłach następników, odwiedzanego węzła eb. Jeżeli któryś z następników zawiera poszukiwaną wartość klucza, ustalane są parametry wyjściowe procedury, wskazujące na węzeł znaleziony ebz i węzeł jego ojca epz. Jeżeli żaden z następników nie zawiera poszukiwanego klucza, to dopóki kolejny węzeł na przeglądanej ścieżce ma dwa następniki, należy wybierać kierunek przeglądania przez lewy lub prawy następnik. Jeżeli węzeł ma tylko jeden następnik, przechodzi się do niego. Procedura nie odwiedza węzłów zewnętrznych. W procedurach Szuk_Pop i Skresl wykorzystuje się omówione już powyżej deklaracje typów z zadania zad49.txt.
PROCEDURE Szuk_Pop(VAR eb,ebz,epz:Wsk; nazwp:St20);
BEGIN
IF(eb^.lewy<>NIL) AND (eb^.prawy<>NIL)
THEN
BEGIN
IF eb^.lewy^.danew.nazwisko=nazwp
THEN
BEGIN
epz:=eb;
ebz:=eb^.lewy
END
ELSE Rys. 15.18.a Oznaczenia do procedury Szuk_Pop
BEGIN
IF eb^.prawy^.danew.nazwisko=nazwp
THEN
BEGIN
epz:=eb;
ebz:=eb^.prawy
END
ELSE
IF nazwp<eb^.danew.nazwisko
THEN Szuk_Pop(eb^.lewy,ebz,epz,nazwp)
ELSE Szuk_Pop(eb^.prawy,ebz,epz,nazwp)
END
END
ELSE
BEGIN
IF (eb^.lewy<>NIL)
THEN Rys. 15.18.b Oznaczenia do procedury Szuk_Pop
BEGIN
IF eb^.lewy^.danew.nazwisko=nazwp
THEN
BEGIN
epz:=eb;
ebz:=eb^.lewy
END
Rys 15.18.c. Oznaczenia do procedury Szuk_Pop
ELSE Szuk_Pop(eb^.lewy,ebz,epz,nazwp)
END
ELSE
IF (eb^.prawy<>NIL)
THEN
BEGIN
IF eb^.prawy^.danew.nazwisko= nazwp
THEN
BEGIN
epz:=eb;
ebz:=eb^.prawy
END
ELSE Szuk_Pop(eb^.prawy,ebz,epz,nazwp)
END
END
END; {Szuk_Pop}
Ta procedura jest długa, ale jest szybka w działaniu i łatwa do analizy. Odwiedzając węzeł przodka, bada się jego następniki i nie odwiedza się pustych następników.
To samo działanie znalezienia węzła usuwanego i jego przodka można zapisać krócej, podobnie jak w funkcji SzukajR, zdefiniowanej powyżej, zmodyfikowanej tak, aby dodatkowo jako efekt uboczny zwracała wskaźnik do elementu przodka, węzła usuwanego.
FUNCTION SzukajPR(eb:Wsk; VAR epz:Wsk; nazwp:St20):Wsk;
BEGIN
IF (eb=NIL) OR (eb^.danew.nazwisko=nazwp)
THEN SzukajPR:=eb
ELSE
IF nazwp<eb^.danew.nazwisko
THEN SzukajPR:=SzukajPR(eb^.lewy,eb,nazwp)
ELSE SzukajPR:=SzukajPR(eb^.prawy,eb,nazwp)
END; {SzukajPR}
Funkcja SzukajPR, bada węzeł odwiedzany, którym jest kolejny lewy lub prawy węzeł na ścieżce. W przypadku nieznalezienia poszukiwanego klucza, odwiedza także węzeł pusty. Wskaźnik do przodka węzła badanego jest przekazywany jako parametr funkcji rekurencyjnej. Zastosowanie tej funkcji, w omówionej poniżej procedurze Skresl, wymagałoby wywołania funkcji SzukajPR, zamiast procedury Szuk_Pop.
Procedura Skresl, usuwająca węzeł z drzewa, wprowadza poszukiwane nazwisko i ustala wartości początkowe wskaźników: do węzła bieżącego ws, węzła znalezionego wsz i węzła poprzedzającego znaleziony wpz. Następnie sprawdza, czy poszukiwane nazwisko znajduje się w danych węzła korzenia. Jeżeli tak, to węzłem usuwanym wsz jest korzeń drzewa, w przeciwnym przypadku węzeł usuwany i węzeł jego ojca zostanie znaleziony przez procedurę Szuk_Pop. Jeżeli węzeł usuwany nie ma lewego poddrzewa węzłem zamieniającym wz, będzie węzeł prawy węzła usuwanego, w przeciwnym przypadku jego węzeł lewy. W przypadku, gdy węzłem zamieniającym jest węzeł lewy usuwanego, należy znaleźć skrajny prawy węzeł, lewego poddrzewa wd i do niego dołączyć prawe poddrzewo węzła usuwanego. Na zakończenie węzeł zamieniający zostaje wpisany do odpowiedniego następnika, węzła wpz - ojca węzła usuwanego. W przypadku, gdy usunięto korzeń staje się nowym korzeniem drzewa. Procedura Skresl wykorzystuje zmienną globalną korzen.
PROCEDURE Skresl;
VAR
nazw:St20;
j :INTEGER;
ws, {wezel bieżący}
wsz, {wezel usuwany}
wpz, {wezel poprzedni usuwanego}
wz, {wezel zamieniający}
wd:PWezel; {wezel do którego dołączane jest
prawe poddrzewo węzła usuwanego}
BEGIN
CLRSCR;
IF korzen=NIL
THEN WRITELN('Drzewo puste')
ELSE
BEGIN
WRITE('Podaj NAZWISKO: ');
READLN(nazw);
ws:=korzen;
wsz:=NIL;
wpz:=NIL;
IF ws^.danew.nazwisko=nazw
THEN wsz:=ws
ELSE Szuk_Pop(korzen,wsz,wpz,nazw);
IF wsz=NIL
THEN WRITELN('Nie znaleziono wskazanej osoby')
ELSE
BEGIN
IF wsz^.lewy=NIL
THEN wz:=wsz^.prawy
ELSE
BEGIN
wz:=wsz^.lewy;
wd:=wz;
WHILE wd^.prawy<>NIL DO
wd:=wd^.prawy;
wd^.prawy:=wsz^.prawy
END;
IF wpz=NIL
THEN korzen:=wz Rys. 15.19 Oznaczenia do procedury Skresl
ELSE
IF wpz^.lewy=wsz
THEN wpz^.lewy:=wz
ELSE wpz^.prawy:=wz;
lw:=lw-1;
DISPOSE(wsz)
END
END
END; {Skresl}
Algorytm 1 zaimplementowano poniżej, w procedurze UsunDane. Wykorzystuje ona procedurę Szuk_Nazw, znajdującą w drzewie węzeł, zawierający poszukiwane nazwisko nazwp, a także procedury MinPrawego i MaxLewego, służące do znalezienia potomka "w porządku". MinPrawego poszukuje węzła z minimalną wartością klucza w prawym poddrzewie. MaxLewego poszukuje węzła z maksymalną wartością klucza w lewym poddrzewie. We wszystkich tych procedurach wykorzystuje się typ wskaźnikowy PWezel2, zdefiniowany powyżej.
PROCEDURE Szuk_Nazw(VAR b,p:PWezel2; nazwp:St20; VAR Znal:BOOLEAN);
BEGIN
Znal:=FALSE;
IF b=NIL
THEN WRITELN('Nie znaleziono poszukiwanej osoby')
ELSE
IF b^.DaneWezla.nazwisko=nazwp
THEN Znal:=TRUE
ELSE
IF nazwp<b^.DaneWezla.nazwisko
THEN Szuk_Nazw(b^.lewy,b,nazwp)
ELSE Szuk_Nazw(b^.prawy,b,nazwp)
END; {Szuk_Nazw}
PROCEDURE MinPrawego(VAR b,p:PWezel2);
BEGIN
WHILE b^.lewy<>NIL DO
BEGIN
p:=b;
b:=b^.lewy;
END
END; {MinPrawego}
PROCEDURE MaxLewego(VAR b,p:PWezel2);
BEGIN
WHILE b^.prawy<>NIL DO
BEGIN
p:=b;
b:=b^.prawy;
END
END; {MaxLewego}
Procedura UsunDane wyszukuje w drzewie węzeł usuwany, wskazywany przez b oraz jego przodka p. Jeżeli usuwany jest węzeł liścia i jednocześnie jest on węzłem korzenia, to drzewo staje się puste. Jeżeli węzeł liścia nie jest korzeniem, to zeruje się odpowiedni następnik w jego przodku w zależności, czy węzeł usuwany jest prawym, czy lewym potomkiem swego przodka. W obydwu przypadkach węzeł liścia jest zwalniany. Jeżeli węzeł usuwany nie jest liściem i ma prawego potomka, węzeł zamieniający jest pobierany z prawego poddrzewa. Do węzła usuwanego dk, są wpisywane dane z węzła zamieniającego. Jeżeli węzeł zamieniający b, jest bezpośrednim potomkiem węzła usuwanego, to do węzła usuwanego, jako prawe poddrzewo jest dołączane prawe poddrzewo węzła zamieniającego. W tym przypadku węzeł zamieniający nie ma lewego poddrzewa, bo inaczej nie byłby zamieniającym. Jeżeli węzeł zamieniający nie jest bezpośrednim potomkiem węzła usuwanego, to może być liściem, lub nie może mieć lewego poddrzewa. W tym przypadku do przodka p, węzła zamieniającego b, jako jego lewe poddrzewo jest podłączane prawe poddrzewo węzła zamieniającego b. Węzeł zamieniający jest zwalniany.
Jeżeli węzeł usuwany nie jest liściem, ale nie ma prawego potomka, jest zamieniany maksymalną wartością z lewego poddrzewa. Do węzła usuwanego dk, są wpisywane dane z węzła zamieniającego. Jeżeli węzeł zamieniający b, jest lewym bezpośrednim potomkiem węzła usuwanego, to do węzła usuwanego jako lewe poddrzewo jest dołączane lewe poddrzewo węzła zamieniającego. W tym przypadku węzeł zamieniający nie ma prawego poddrzewa, bo inaczej nie byłby zamieniającym. Jeżeli węzeł zamieniający nie jest bezpośrednim potomkiem węzła usuwanego, to może być liściem, lub nie może mieć prawego poddrzewa. W tym przypadku do przodka węzła zamieniającego p, jako jego prawe poddrzewo jest podłączane lewe poddrzewo węzła zamieniającego b. Węzeł zamieniający jest zwalniany.
PROCEDURE UsunDane;
VAR
dk,b,p:PWezel2;
nazw :st20;
Znal :BOOLEAN;
BEGIN
WRITE('Podaj NAZWISKO: ');
READLN(nazw);
b:=korzen;
SzukNazw(b,p,nazw,Znal); {pierwszy parametr przekazuje
adres węzła usuwanego}
IF Znal
THEN
BEGIN
dk:=b;
IF (b^.prawy=NIL) AND (b^.lewy=NIL)
THEN
BEGIN
IF b=korzen
THEN korzen=NIL;
ELSE
IF b=p^.prawy
THEN p^.prawy:=NIL
ELSE p^.lewy:=NIL;
DISPOSE(b);
END
ELSE
IF b^.prawy<>NIL
THEN
BEGIN
p:=b;
b:=b^.prawy; Rys.15.20. Oznaczenia do procedury UsunDane
MinPrawego(b,p);
dk^.DaneWezla:=b^.DaneWezla;
IF b=dk^.prawy
THEN dk^.prawy:=b^.prawy
ELSE p^.lewy:=b^.prawy;
DISPOSE(b);
END
ELSE
BEGIN
p:=b;
b:=b^.lewy;
MaxLewego(b,p);
dk^.DaneWezla:=b^.DaneWezla;
IF b=dk^.lewy
THEN dk^.lewy:=b^.lewy
ELSE p^.prawy:=b^.lewy;
DISPOSE(b);
END
END
END; {UsunDane}
Drzewo wielokierunkowe
Drzewo, w którym każdy węzeł może mieć więcej niż dwóch potomków, może także być przedstawione za pomocą drzewa dwójkowego, jednak z inną interpretacją łączników węzła niż w drzewie BST.
Jeżeli łączniki węzła drzewa dwójkowego wskazują na:
kolejny węzeł tego samego poziomu, czyli węzeł brata (węzeł alternatywny),
węzeł pierwszego potomka (węzeł sekwencyjny),
to drzewo tego typu jest nazywane drzewem wielokierunkowym [Wirth]. Konwersja drzewa dowolnego stopnia na drzewo wielokierunkowe, jest pokazana na rysunku 15.21, na przykładzie drzewa z rysunku 15.1.
Rys. 15.21. Konwersja drzewa stopnia n>2 do drzewa wielokierunkowego
Przy dołączaniu węzłów do takiego drzewa należy podawać numer poziomu dla każdego węzła i wprowadzać dane ścieżkami od węzła korzenia do węzła liścia, z powtarzaniem tylko różniących się fragmentów następnej ścieżki. Kolejność wprowadzania poziomów i węzłów dla drzewa z rys 15.21 byłaby następująca:
1 A
2 B
3 D
4 I
4 J
3 E
4 K
4 L
4 M
2 C
3 F
4 N
3 G
4 O
4 P
4 R
3 H
4 S
Aby umożliwić iteracyjne przeglądanie takiego drzewa, które wymaga cofania się do węzła ojca, węzeł powinien dodatkowo zawierać łącznik do węzła ojca. Typ węzła dla drzewa wielokierunkowego zdefiniowano jako TWezel3.
TYPE
PWezel3=^TWezel3;
TWezel3=RECORD
poziom :BYTE;
DaneWezla:TDane;
ojciec,
brat,
syn :PWezel3;
END;
Procedura dołączająca nowy węzeł do drzewa, otrzymuje przez parametry: wskaźnik do ostatnio dołączonego węzła Ostatni, wskaźnik do korzenia węzła oraz numer poziomu węzła dołączanego pwd. Jeżeli numer poziomu nie jest prawidłowy, procedura wyświetla komunikat o błędzie i sygnalizuje go ustawieniem parametru wyjściowego Blad. Procedura wczytuje dane do nowego węzła za pomocą procedury Wprowadz. Jeżeli poziom węzła dołączanego jest większy, niż węzła ostatnio wprowadzanego, to nowy węzeł jest dołączany jako węzeł syna, którego ojcem jest węzeł Ostatni. Jeżeli poziom węzła dołączanego jest równy poziomowi węzła Ostatni, to nowy węzeł jest kolejnym potomkiem węzła, którego potomkiem był Ostatni i jest dołączany do niego, jako węzeł brata. Jego ojcem jest ojciec ostatniego. Jeżeli poziom węzła dołączanego jest mniejszy niż poziom węzła Ostatniego to znaczy, że dołączany węzeł jest kolejnym potomkiem węzła wcześniej dołączonego. W tym przypadku należy cofnąć się po drzewie, aby znaleźć potomka tego węzła, znajdującego się na tym samym poziomie, co węzeł dołączany. We wszystkich przypadkach węzeł dołączany zostanie zapamiętany jako Ostatni. Ta procedura zakłada, że węzły drzewa są wprowadzane ścieżkami, ponieważ sam numer poziomu węzła nie identyfikuje jego węzła ojca. Jeżeli podczas cofania się dojdzie się do korzenia, a węzeł o podanym numerze poziomu nie zostanie znaleziony, oznacza to, że wprowadzone dane nie tworzą spójnego drzewa.
PROCEDURE Dolacz
{procedura sprawdza poprawność poziomu, wpisuje poziom do
rekordu węzła i dołącza rekord węzła do drzewa}
(VAR pwd :BYTE; {poziom węzła}
VAR Korzen, {wskaźnik na korzeń}
Ostatni :PWezel3; {wskaźnik ostatni dołączony węzeł}
VAR Blad :BOOLEAN); {sygnalizacja niespójności danych drzewa}
VAR
wb:PWezel3; {adres bieżącego węzła}
BEGIN
NEW(wb);
Blad:=FALSE;
WITH wb^ DO
BEGIN
syn:=NIL;
brat:=NIL;
poziom:=pwd;
Wprowadz(wb^.DaneWezla);
END;
IF Ostatni=NIL
THEN korzen:=wb
ELSE
IF pwd>Ostatni^.poziom
THEN
BEGIN
Ostatni^.syn:=wb;
wb^.ojciec:=Ostatni
END
ELSE
IF pwd=Ostatni^.poziom
THEN
BEGIN
Ostatni^.brat:=wb;
wb^.ojciec:=Ostatni^.ojciec
END
ELSE
BEGIN
WHILE (Ostatni<>Korzen) AND (pwd<>Ostatni^.poziom) DO
Ostatni:=Ostatni^.ojciec;
IF pwd=Ostatni^.poziom
THEN
BEGIN
Ostatni^.brat:=wb;
wb^.ojciec:=Ostatni^.ojciec
END
ELSE
IF Ostatni=Korzen
THEN
BEGIN
WRITELN('***drzewo niespojne');
Blad:=TRUE;
EXIT
END
END;
Ostatni:=wb
END; {Dol_Wez}
Procedura Wyprowadz_Drzewo, pozwala zorientować się w strukturze utworzonego drzewa. Dla każdego węzła drzewa wyświetla tylko jego poziom. Drzewo przeglądane jest ścieżkami: pierwsza ścieżka od korzenia do końca ścieżki, kolejne ścieżki od rozgałęzienia części wspólnej ścieżki do końca ścieżki. Procedura zlicza liczbę węzłów drzewa w zmiennej globalnej lw.
PROCEDURE Wyprowadz_Drzewo(VAR wb:PWezel3);
BEGIN
IF wb<>NIL
THEN
BEGIN
WRITELN('-------------------------------------');
WRITELN('poziom ',wb^.poziom);
Wyprowadz_Drzewo(wb^.syn);
lw:=lw+1;
Wyprowadz_Drzewo(wb^.brat)
END
END; {Wyprowadz_Drzewo}
1.1.1
1.1.1
1.1.2
1.1.3
1.2.
1.2.1
1.2.2
1.2.3
1.2.4
2.
2.1.
2.1.1.
2.1.2.
2.1.3.
2.2.
2.3.
3.
3.1
3.1.1.
3.1.1.1
3.1.1.2
3.1.2.
3.1.3.
3.2
3.3
3.4
Program główny wykorzystuje zmienne, które powinny być w nim zadeklarowane. W pętli wczytuje numer poziomu kolejnego węzła na ścieżce i dołącza nowy węzeł w odpowiednim miejscu drzewa, po czym pokazuje stan drzewa za pomocą procedury Wyprowadz_Drzewo.
BEGIN {Program główny}
Korzen:=NIL;
Ostatni:=NIL;
lw:=0;
REPEAT
WRITE('Podaj poziom ');
READLN(poziomd);
Dolacz(poziomd,Korzen,Ostatni,bladdanych);
WRITE('Czy kontynuujesz wprowadzanie drzewa ');
READLN(odp);
UNTIL odp IN ['n','N'];
Wyprowadz_Drzewo(korzen)
END. {Drzewa}
Drzewo jest strukturą hierarchiczną. Poszczególne węzły, opisujące elementy struktury hierarchicznej, można też numerować hierarchicznie np. tak jak rozdziały i podrozdziały książki w skorowidzu. Symbole kropki oddzielają numery kolejnych poziomów. Numery po znaku kropki są numerami węzłów potomnych węzła nadrzędnego i są numerowane kolejno w obrębie węzła nadrzędnego. W przypadku takiej numeracji węzły potomków można wprowadzać w dowolnej kolejności, jednak przy założeniu, że ich węzeł ojca będzie wprowadzony przed węzłami potomków.
Rys. 15.24. Drzewa skorowidza a) struktura skorowidza b)drzewo zwykłe c) drzewo wielokierunkowe
Dołączanie do takiego drzewa oraz odczytywanie drzewa, w celu np. wydrukowania skorowidza, wymaga wydzielania kolejnych części hierarchicznych numerów węzła, wstawianego i węzła przeglądanego i uwzględniania ich przy określaniu kierunku poruszania się po drzewie. Na każdym poziomie drzewa, identyfikatorem węzła będzie odpowiednia część hierarchicznego numeru: dla poziomu 1 liczba przed pierwszą kropką, dla poziomu 2 - liczba po pierwszej kropce, dla poziomu 3 liczba po drugiej kropce itd. Dopóki numer węzła wstawianego, jest większy od węzła przeglądanego, przechodzi się do następnego węzła brata. Jeżeli numery się zrównają przechodzi się na następny poziom, według adresu węzła syna, po czym następuje zmiana identyfikatorów węzłów na identyfikatory aktualnego poziomu. Odpowiednie procedury, dołączania nowego węzła i wyprowadzania zawartości skorowidza, można napisać analogicznie do omówionych powyżej.
Zasady i styl programowania
Drzewa stosuje się do przedstawienia hierarchicznych struktur danych, w których nie ma połączeń pomiędzy tymi samymi poziomami różnych poddrzew.
Operacje wykonywane na drzewie mogą być zapisywane w postaci procedur rekurencyjnych i iteracyjnych. Na ogół zapis rekurencyjny jest bardziej zwarty i czytelny. Procedura rekurencyjna wykonująca operacje na drzewie zawiera dwa swoje wywołania rekurencyjne jedno, w którym parametrem jest adres lewego poddrzewa i drugie, którego parametrem jest adres prawego poddrzewa, aktualnie odwiedzanego węzła.
Procedury rekurencyjne nie mogą nadawać wartości początkowych zmiennym, które mają być ustalone tylko jeden raz dla całego drzewa, ani też wprowadzać danych wymaganych do zrealizowania operacji wykorzystującej rekurencję. Te dane muszą zostać ustalone lub wprowadzone, w procedurze wywołującej procedurę rekurencyjną lub w programie. Także wyniki obliczone dla całego drzewa muszą być wyprowadzone jeden raz, poza procedurą rekurencyjną. Dlatego też w przykładach zamieszczonych w ramach ćwiczenia, zdefiniowano procedury rekurencyjne jako procedury lokalne procedur, realizujących określoną operację na drzewie. Procedura nadrzędna przygotowuje dane, wywołuje procedurę rekurencyjną i wyprowadza jej wyniki, a jej procedura lokalna realizuje operację na drzewie z wykorzystaniem rekurencji.
Procedury rekurencyjne dla drzewa mogą być zdefiniowane tak, że odwiedzane są wyłącznie węzły wewnętrzne, lub odwiedzane są zarówno węzły wewnętrzne jak i węzły zewnętrzne. Te ostatnie zawierają mniej warunków, ale powodują jedno dodatkowe wywołanie rekurencyjne dla pustego węzła, znajdującego się na końcu każdej ścieżki. W celu przyspieszenia operacji przeglądania drzewa, powinno się stosować procedury, które kończą wywołania rekurencyjne, przy dojściu do końca ścieżki.
Podobnie jak dla operacji, realizowanych przez rekurencję na innych strukturach danych, kolejność działań wykonywanych na węźle oraz wywołań rekurencyjnych może mieć istotny wpływ na uzyskiwane efekty. Niektóre wyniki obliczeń, wykonywanych na wszystkich węzłach drzewa jednak nie zależą od sposobu przeglądania drzewa. Dla konkretnych zadań, realizowanych za pomocą procedury rekurencyjnej należy więc dokładnie przeanalizować, czy sposób przeglądania drzewa jest istotny, czy nie. Jeżeli jest istotny, należy dobrać właściwy sposób przeglądania drzewa.
Drzewa binarne, implementowane przez struktury dynamiczne wykorzystuje się wtedy, gdy liczba danych przechowywanych często się zmienia i dane są często przeszukiwane. Element poszukiwany, lub miejsce wstawienia nowego elementu do uporządkowanej struktury danych, w postaci drzewa binarnego, można znaleźć dla n elementów w czasie proporcjonalnym do log(n), a więc znacznie szybciej niż w liście, gdzie czas wyszukiwania wynosi średnio n/2. Dla listy przeszukuje się średnio połowę listy, a w drzewie tylko połowę ścieżki.
Drzewa binarne mogą mieć zastosowanie do szybkiego posortowania zbioru kluczy. Czas sortowania jest proporcjonalny do iloczynu liczby kluczy N i czasu wyszukiwania w drzewie logN, co jest znacznie szybsze niż sortowanie przy użyciu metod o złożoności kwadratowej (sortowanie przez selekcję, sortowanie bąbelkowe, sortowanie przez wstawianie - umieszczanie [Syslo])
Drzewa binarne mogą być wykorzystywane do przyspieszenia operacji wykonywanych na pliku, podobnie jak listy, (co było omówione w p. 14.10). Posortowane drzewo binarne o węzłach, zawierających klucz i położenie rekordu w pliku, może stanowić indeks pliku. W drzewie można szybko znaleźć numer elementu pliku, zawierającego poszukiwany klucz. Bardzo szybko też można stwierdzić, że poszukiwanego elementu nie ma w pliku. W tym przypadku, wystarczy przeszukać do końca ścieżkę w drzewie indeksu. Aby stwierdzić, że elementu nie ma w pliku nieposortowanym, należałoby przeszukać cały plik do końca.
Można dla jednego nieposortowanego pliku, utworzyć kilka drzew indeksów, wykorzystujących różne pola rekordu danych, jako klucz do sortowania drzewa indeksu.
Drzewo indeksu, utworzone dla pliku danych, powinno też być składowane w pliku indeksu, do czasu następnej pracy z programem, obsługującym plik. Kasowane logicznie rekordy danych z pliku, powinny mieć usuwane węzły z drzewa indeksu, natomiast powinny dalej fizycznie pozostawać w pliku. Okresowo jednak trzeba przepisywać nieskasowane elementy pliku do nowego pliku, oraz tworzyć na jego podstawie nowe drzewo indeksów.
Drzewa binarne zrównoważone wykorzystuje się w roli słowników, dla których częstość wyszukiwania jest znacznie większa, niż częstość wstawiania. Na przykład można dla kartotek rekordów tworzyć słowniki wartości pól, powtarzających się w wielu rekordach (słownik imion, zawodów, stanowisk, kolorów, miast, itp.).
Drzewa w postaci stogu są wykorzystywanie w algorytmie sortowania stogowego (nazywanego też algorytmem sortowania przez kopcowanie). Dane z węzłów drzewa pełnego, wpisanego do tablicy, lub utworzonego za pomocą procedury DW, muszą zostać odpowiednio przesiane, aby przywrócić drzewu własność stogu. Następnie wybiera się ze stogu kolejne elementy o maksymalnej wartości klucza, z elementów jeszcze nie wybranych przestawia się je na początku posortowanej części stogu. Przed rozpoczęciem sortowania, długość posortowanej części ciągu jest równa zero i pierwszy "wysiany element, o maksymalnej wartości, jest lokowany w ostatnim elemencie stogu, który jest przestawiany do wierzchołka, po czym znowu musi zostać przesiany. Algorytm sortowania stogowego można znaleźć w [Wirth i jest ilustrowany w pakiecie EI]
Stog jest też wykorzystywany jako kolejka priorytetowa. Elementy z takiej kolejki są pobierane zawsze z korzenia stogu. Następnie w korzeniu umieszcza się ostatni element stogu, który musi zostać przesiany, aby w korzeniu znalazł się ponownie element o najwyższym priorytecie. Wysianie kolejnego elementu o najwyższym priorytecie jest realizowane wzdłuż ścieżki drzewa. Złożoność wykonania tej operacji jest więc logarytmiczna
Stóg może być wykorzystywany jako pomocnicza struktura danych do sortowania plików przez scalanie serii uporządkowanych. Służy wtedy do zwiększania długości sortowanych serii [wirth].
Pytania kontrolne
Wymień podstawowe cechy grafu, który jest drzewem.
Omów definicje bezpośredniego przodka i bezpośrednich potomków węzła drzewa.
Czym różni się węzeł korzenia od pozostałych węzłów?
Czym różnią się węzły liści od pozostałych węzłów?
Co to jest rozmiar drzewa?
Co to jest stopień drzewa?
Co to jest głębokość węzła i głębokość drzewa?
Czym charakteryzuje się drzewo pełne?
Omów definicję typu węzła drzewa stopnia d.
Omów definicję typu węzła drzewa binarnego.
Jak można drzewo binarne przedstawić w tablicy?
Jaka zasada dotycząca uporządkowania kluczy jest stosowana w binarnym drzewie poszukiwań?
Jakie relacje zachodzą pomiędzy kluczami węzłów sąsiednich poziomów w stogu?
Jak wyszukuje się w drzewie binarnym węzeł, który będzie węzłem bezpośredniego przodka dla węzła dołączanego?
Napisz ciąg 10 liczb i utwórz drzewo binarne, w którym liczby ciągu będą stanowiły klucze węzłów.
Jak odbywa się wyszukiwanie węzła, o podanej wartości klucza. Jak określa się liczbę porównań, które trzeba wykonać, w celu znalezienia węzła drzewa, o poszukiwanej wartości klucza?
Na czym polega wykorzystanie węzła wartownika i czemu służy?
Omów dlaczego procedury rekurencyjne są bardziej odpowiednie dla realizacji operacji na drzewie niż procedury iteracyjne Jak wygląda budowa takiej procedury?
Omów sposoby przeglądania drzew, przy założeniu, że węzeł lewy jest odwiedzany przed węzłem prawym.
Dla utworzonego wcześniej drzewa binarnego, określ wysokość i głębokość wszystkich węzłów
Ponumeruj węzły drzewa, w kolejności wykonywania na nich operacji, dla sposobów przeglądania drzewa: pre order, in order i post order.
Jaki sposób przeglądania drzewa należy zastosować, w celu wyprowadzenia kluczy w porządku wzrastającym?
Jaki sposób przeglądania drzewa należy zastosować, w celu wyprowadzenia kluczy w porządku malejącym?
Jaki sposób przeglądania należy zastosować przy składowaniu danych z węzłów drzewa w pliku, aby po odtworzeniu otrzymać drzewo o takim samym kształcie?
Jak sposób przeglądania drzewa wyrażenia wpływa na notację zapisu wyrażenia?
Jaka jest zasada usuwania z drzewa węzła liścia?
Jaka jest zasada usuwania z drzewa węzła, który ma jednego bezpośredniego potomka?
Jakie są algorytmy usuwania z drzewa węzła, który ma dwóch bezpośrednich potomków? Zilustruj je na rysunku.
Dla jakich drzew powinno się stosować drzewo wielokierunkowe? Narysuj dowolne drzewo stopnia 3 i przedstaw je w formie drzewa wielokierunkowego.
Ćwiczenie - Drzewa binarne
Celem ćwiczenia jest zapoznanie się z możliwością grupowania rekordów w strukturze drzewa oraz z budową i działaniem procedur rekurencyjnych. W tym celu należy opracować zbiór procedur realizujących podstawowe algorytmy na strukturze drzewiastej, na przykładzie drzewa binarnego reprezentującego kartotekę danych. Do tych algorytmów należą: tworzenie drzewa, wyświetlanie zawartości węzłów drzewa, wyszukiwanie w drzewie węzła spełniającego określony warunek, wybieranie zbioru węzłów, spełniających określony warunek, usuwanie węzła z drzewa, wykonywanie obliczeń na danych z węzłów drzewa.
Na podstawie przykładów z ćwiczenia do rozdziału 9, tj.
przykładu 1.1 opisującego rekord konta bankowego,
przykładu 2.1 zawierającego procedurę wprowadzania danych do rekordu,
przykładu 3.1 podającego procedurę wyświetlania danych z rekordu,
oraz podanych poniżej procedur tworzenia kartoteki kont w postaci drzewa, należy napisać program, tworzący własną kartotekę danych w postaci drzewa binarnego.
Do zrealizowania programu można wykorzystać moduł obsługi typu rekordowego, opracowany w ramach realizacji zadania z ćwiczenia do rozdziału 11. Można też zdefiniować i wykorzystać moduł obsługi struktury danych w postaci drzewa BST lub zdefiniować procedury i funkcje, działające na drzewie bezpośrednio w programie tak, jak w przykładach zamieszczonych poniżej.
1. Zdefiniować typ rekordowy, określający strukturę węzła. Zadeklarować zmienną reprezentującą wskaźnik do korzenia drzewa.
Przykład 1.
Poniżej zamieszczono definicję typu rekordu węzła drzewa z danymi typu TKonto. Rekord zawiera wskaźniki do lewego i prawego poddrzewa. Deklaracja zmiennej, wskazującej na korzeń drzewa wykorzystuje zdefiniowany typ wskaźnikowy PWezel.
TYPE
PWezel=^TWezel;
TWezel=RECORD
dane :TKonto;
lewy,
prawy:PWezel
END;
VAR
korzen:PWezel;
2. Opracować procedurę zakładania kartoteki danych w postaci drzewa binarnego.
Przykład 2.
Procedura Generuj_Drzewo tworzy kartotekę w postaci drzewa rekordów. Kluczem przy tworzeniu drzewa jest pole saldo. Dane do rekordu węzła są wczytywane z klawiatury za pomocą procedury Wprowadz_Rek. Nowy rekord jest dołączany na końcu ścieżki, wybieranej wg. relacji pomiędzy saldem rekordu wstawianego, a saldem badanego rekordu drzewa, za pomocą procedury Wstaw. Procedura Wstaw przydziela numery kont, kolejnym węzłom dołączanym do drzewa, pamiętając numer ostatnio przydzielonego konta w zmiennej NumerKonta. Po wprowadzeniu danych i dołączeniu rekordu do drzewa, procedura pyta o zakończenie operacji. Aby było możliwe dołączanie nowych węzłów do już istniejącego drzewa, początkowa wartość zmiennej korzen musi zostać ustalona w programie głównym.
PROCEDURE Generuj_Drzewo(VAR korzen:PWezel);
VAR
rekord:TKonto;
odp :CHAR;
PROCEDURE Wstaw(rekord:TKonto; VAR wezel:PWezel);
BEGIN
IF wezel=NIL
THEN
BEGIN
NEW(wezel);
WITH wezel^ DO
BEGIN
dane:=rekord;
lewy:=NIL;
prawy:=NIL
END
END
ELSE
IF rekord.saldo<wezel^.dane.saldo
THEN Wstaw(rekord,wezel^.lewy)
ELSE Wstaw(rekord,wezel^.prawy)
END; {Wstaw}
BEGIN {Generuj_Drzewo}
REPEAT
NumerKonta:= NumerKonta+1;
Wprowadz_Rek(rekord,NumerKonta);
Wstaw(rekord,korzen);
WRITE('Czy koniec wczytywania ? (T LUB N)');
READLN(odp);
UNTIL odp IN ['T','t']
END; {Generuj_Drzewo}
Wywołanie tej procedury ma postać: Generuj_Drzewo(korzen);
3. Opracować procedurę wyświetlania danych z węzłów drzewa w różnych postaciach graficznych.
Przykład 3.1
Procedura Pokaz_Drzewo wyświetla jedną daną z każdego węzła drzewa w pewnej formie graficznej. Wykorzystuje rekurencyjną procedurę Pokaz, która wyświetla pole saldo z wszystkich rekordów z zaznaczeniem struktury drzewa. Drzewo jest wyświetlane na ekranie od lewej do prawej, przy czym wartości pola saldo rosną w kierunku dołu ekranu. Dane z węzłów znajdujących się na tym samym poziomie, są wyświetlane w tej samej kolumnie.
PROCEDURE Pokaz_Drzewo;
PROCEDURE Pokaz(wezel:PWezel; poziom:INTEGER);
VAR
i:INTEGER;
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
Pokaz( lewy,poziom+1);
FOR i:=1 TO poziom DO
WRITE(' ');
WRITELN(dane.saldo);
Pokaz( prawy,poziom+1)
END
END; {Pokaz}
BEGIN {Pokaz_Drzewo}
IF korzen<>NIL
THEN Pokaz(korzen,0)
ELSE WRITELN('Drzewo jest puste ');
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN
END; {Pokaz_Drzewo}
Określ jaki sposób przeglądania drzewa zastosowano w procedurze Pokaz_Drzewo. Jak należy przeglądać drzewo, aby procedura wyprowadzała wartości pola saldo, w porządku malejącym, w kierunku dołu ekranu.
Przykład 3.2.
Procedura Przegladaj _Drzewo wyświetla dane wszystkich rekordów drzewa, za pomocą rekurencyjnej procedury Przegladaj. Dane z rekordu węzła są wyświetlane przez procedurę Wyswietl_Rek, w kolejności wzrastającej wartości pola saldo. Procedura Przegladaj stosuje przeglądanie drzewa in order.
PROCEDURE Przegladaj_Drzewo(korzen:PWezel);
PROCEDURE Przegladaj(wezel:PWezel);
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
Przegladaj(lewy);
Wyswietl_Rek(wezel^.dane);
Przegladaj(prawy)
END
END; {Przegladaj}
BEGIN {Przegladaj_Drzewo}
IF korzen<>NIL
THEN Przegladaj(korzen);
ELSE WRITELN('Drzewo jest puste ');
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN
END; {Przegladaj_Drzewo}
Rozważ zmiany, które należy wprowadzić w procedurze, jeżeli wartości pola saldo miałyby maleć w kierunku dołu ekranu.
4. Opracować procedurę wyszukiwania węzła, którego dane spełniają określony warunek.
Przykład 4.1
Procedura Szukaj_Salda przeszukuje drzewo w celu znalezienia węzła drzewa, które w polu saldo zawiera wartość, podaną przez użytkownika z klawiatury. Procedura wykorzystuje rekurencyjną funkcję Szukaj, która porównuje pole saldo w rekordach, znajdujących się na wybieranej podczas przeszukiwania ścieżce, z wartością przekazaną jako parametr procedury. Funkcja przegląda ścieżkę, aż do znalezienia węzła o poszukiwanej wartości klucza, lub osiągnięcia końca ścieżki, gdy węzła o poszukiwanej wartości klucza nie znaleziono w drzewie. Przed wywołaniem funkcji należy przygotować wartość parametru, stanowiącego wartość salda poszukiwanego konta, zależną od decyzji użytkownika. Po wywołaniu funkcji należy wyświetlić dane ze znalezionego węzła, w przypadku znalezienia poszukiwanego rekordu lub wyprowadzić komunikat w przypadku nieznalezienia.
PROCEDURE Szukaj_Salda(korzen:PWezel);
VAR
wartosc_szukana:LONGINT;
wp :PWezel;
FUNCTION Szukaj(wezel:PWezel; wartosc:INTEGER):PWezel;
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
IF dane.saldo=wartosc
THEN
BEGIN
WRITELN(wezel^.dane.nazwisko_imie, ' saldo ',
wezel^.dane.saldo);
Szukaj:=wezel
END
ELSE
IF wartosc<dane.saldo
THEN Szukaj:=Szukaj(lewy,wartosc)
ELSE Szukaj:=Szukaj(prawy,wartosc)
END
ELSE Szukaj:=NIL
END; {Szukaj}
BEGIN{Szukaj_Salda}
WRITELN('Podaj wartosc poszukiwanego salda ');
READLN(wartosc_szukana);
wp:=Szukaj(korzen,wartosc_szukana);
IF wp=NIL
THEN WRITELN('Nie znaleziono !')
ELSE Wyswietl_Rek(wp^.dane);
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN;
END; {Szukaj_Salda}
Przykład 4.2
Procedura Szukaj_w_Drzewie przeszukuje drzewo w celu znalezienia węzła drzewa, którego pole nr_konta zawiera określony numer, przekazany jako parametr procedury. Procedura wykorzystuje rekurencyjną funkcję Szukaj_Numer, która porównuje pole nr_konta w rekordach, drzewa z wartością przekazaną jako parametr procedury. Ponieważ drzewo binarne, zostało uporządkowane według innego pola rekordu konta, to funkcja musi przeglądać całe drzewo, aż do znalezienia węzła o poszukiwanej wartości klucza, co jest sygnalizowane przez parametr Znal lub do zakończenia przeglądania drzewa, gdy węzła o poszukiwanej wartości klucza nie znaleziono w drzewie. Funkcja stosuje przeglądanie pre order, przy czym przy powrocie z rekurencji po znalezieniu węzła nie sprawdza się już węzłów prawego poddrzewa. Przed wywołaniem funkcji należy przygotować wartość parametru, stanowiącego numer poszukiwanego konta, zależną od decyzji użytkownika. Po wywołaniu funkcji należy wyświetlić dane ze znalezionego węzła, w przypadku znalezienia poszukiwanego rekordu lub wyprowadzić komunikat w przypadku nieznalezienia.
PROCEDURE Szukaj_w_Drzewie(korzen:PWezel);
VAR
Jest :BOOLEAN;
num_posz:LONGINT;
wp :PWezel;
FUNCTION Szukaj_Numer(wezel:PWezel; numer:INTEGER;
VAR Znal:BOOLEAN):PWezel;
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
IF dane.nr_konta=numer
THEN
BEGIN
WRITELN(wezel^.dane.nazwisko_imie,' saldo ',
wezel^.dane.saldo);
znal:=TRUE;
Szukaj_Numer:=wezel
END
ELSE
BEGIN
Szukaj_Numer:=Szukaj_Numer(lewy,numer,Znal);
IF NOT Znal
THEN SzukajNumer:=SzukajNumer(prawy,numer,Znal)
END
END
ELSE Szukaj_Numer:=NIL
END; {Szukaj_Numer}
BEGIN {Szukaj_w_Drzewie}
Jest:=FALSE;
WRITELN('Podaj numer poszukiwanego konta ');
READLN(num_posz);
wp:=Szukaj_Numer(korzen,num_posz,Jest);
IF Jest
THEN Wyswietl_Rek(wp^.dane)
ELSE WRITELN('Nie znaleziono');
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN
END;{Szukaj_w_Drzewie}
5. Opracować procedury przeglądania drzewa według różnych algorytmów.
Przykład 5.1.
Procedura Wybierz_Hasla wybiera z drzewa rekordy kont chronionych hasłem, wykorzystując rekurencyjną procedurę Wybierz. Procedura Wybierz wyświetla numery wybranych kont i zlicza je w zmiennej globalnej licznik. Jest ona zadeklarowana w procedurze nadrzędnej Wybierz_Hasla, która także ustala jej wartość początkową i po obliczeniu wyprowadza jej wartość na ekran. Procedura Wybierz przegląda drzewo w kolejności pre order. Kolejność przeglądania drzewa zastosowana w tej procedurze może być dowolna.
PROCEDURE Wybierz_Hasla(korzen:PWezel);
VAR
licznik:INTEGER;
PROCEDURE Wybierz(wezel:PWezel);
BEGIN
IF wezel<>NIL
THEN
BEGIN
IF wezel^.dane.ochrona IN ['t','T']
THEN
BEGIN
INC(licznik);
WRITELN(wezel^.dane.nr_konta);
END;
Wybierz(wezel^.lewy);
Wybierz(wezel^.prawy)
END;
END; {Wybierz}
BEGIN {Wybierz_Hasla}
licznik:=0;
Wybierz(korzen);
IF licznik<>0
THEN WRITELN(' Znaleziono ',licznik,' kont chronionych haslem')
ELSE WRITELN('Nie znaleziono kont chronionych haslem');
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN
END; {Wybierz_Hasla}
Przykład 5.2.
Procedura Przetworz umożliwia przeglądanie drzewa, połączone z przetwarzaniem danych z drzewa. Przetwarzanie jest realizowane przez rekurencyjną procedurę Statystyka, przeglądającą drzewo w kolejności in order. Procedura Statystyka wykonuje obliczenia w zmiennych globalnych, zadeklarowanych w nadrzędnej procedurze Przetworz. Procedura Przetworz ustala ich wartości początkowe, wywołuje przeglądanie drzewa i wyprowadza obliczone wyniki.
PROCEDURE Przetworz(korzen:PWezel);
VAR
min,max,suma,ilosc:LONGINT;
PROCEDURE Statystyka(wezel:PWezel);
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
Statystyka(lewy);
IF dane.saldo>max
THEN max:=dane.saldo
ELSE
IF dane.saldo<min
THEN min:=dane.saldo;
suma:=suma + dane.saldo;
ilosc:=ilosc+1;
Statystyka(prawy)
END
END; {Statystyka}
BEGIN {Przetworz}
max:=korzen^.dane.saldo;
min:=max;
suma:=0;
ilosc:=0;
IF korzen<>NIL
THEN
BEGIN
Statystyka(korzen);
WRITELN(' LICZBA KONT ',ilosc);
WRITELN(' NAJWIEKSZY WKLAD ',max,' ZL');
WRITELN(' NAJMNIEJSZY WKLAD ',min,' ZL');
WRITELN(' SREDNI WKLAD ',suma DIV ilosc,' ZL');
WRITELN(' SUMA WKLADOW ',suma,' ZL');
END
ELSE WRITELN('Drzewo jest puste ');
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN
END; {Przetworz}
Wywołanie tej procedury: Przetworz(korzen);
Przykład 5.3
Procedura Sprawdz wyprowadza numery kont, których salda przekraczają podaną wartość. Przy zastosowaniu przeglądania całego drzewa, w kolejności in order lub pre order, część węzłów będzie odwiedzana niepotrzebnie. Przy przeglądaniu w kolejności odwrotnej do in order, odwiedzając najpierw węzeł prawy, potem środkowy, a na końcu lewy, przeglądanie można zakończyć, jeżeli wartość w węźle jest mniejsza od wartości krytycznej. Przed wywołaniem funkcji należy przygotować wartość parametru, stanowiącego krytyczną wartość salda, zależną od decyzji użytkownika oraz początkową wartość zmiennej licznik. Po wywołaniu funkcji należy wyprowadzić komunikat o liczbie znalezionych rekordów, spełniających warunek wybierania.
PROCEDURE Wybierz_w_Drzewie(korzen:PWezel);
VAR
licznik:INTEGER;
wartosc:LONGINT;
PROCEDURE Sprawdz(wezel:PWezel; wartosc:LONGINT);
BEGIN
IF wezel<> NIL
THEN
BEGIN
Sprawdz(wezel^.prawy)
IF wezel^.dane.saldo>wartosc
THEN
BEGIN
INC(licznik);
WRITELN(wezel^.dane.nr_konta);
Sprawdz(wezel^.lewy);
END
END
END; {Sprawdz}
BEGIN {Wybierz_w_Drzewie}
licznik:=0;
WRITELN('Podaj wartosc krytyczna salda');
READLN(wartosc);
Sprawdz(korzen,wartosc);
WRITELN('Znaleziono ',licznik,' kont z saldem >= ',wartosc);
WRITELN(' Nacisniecie klawisza Enter kontynuuje prace programu ');
READLN;
END; {Wybierz_w_Drzewie}
6. Opracować procedurę kasowania drzewa binarnego.
Przykład 6.
Procedura Usun_Drzewo kasuje wszystkie węzły w drzewie, stosując przeglądanie drzewa post order. Jest to jedyny sposób przeglądania, który można tu zastosować, ponieważ przed skasowaniem każdego węzła, należy skasować najpierw węzły jego potomków. Procedura nie przygotowuje żadnych parametrów, ani nie wymaga wyprowadzania komunikatów, zatem może być wywołana bezpośrednio przez program główny.
PROCEDURE Usun_Drzewo(VAR wezel:PWezel);
BEGIN
IF wezel<>NIL
THEN
WITH wezel^ DO
BEGIN
Usun_Drzewo(lewy);
IF lewy<>NIL
THEN
BEGIN
DISPOSE(lewy);
lewy:=NIL
END;
Usun_Drzewo(prawy);
IF prawy<>NIL
THEN
BEGIN
DISPOSE(prawy);
prawy:=NIL
END
END
END; {Usun_Drzewo}
Wywołanie tej procedury: Usun_Drzewo(korzen);
7. Napisać program główny obsługi kartoteki, zorganizowanej w postaci drzewa BST, wykorzystujący zdefiniowane powyżej typy i procedury.
8. Napisać procedurę składowania danych z kartoteki w postaci drzewa rekordów w pliku i odtwarzania kartoteki na podstawie danych z drzewa. Do dołączania węzłów utworzonych z danych odczytanych z pliku, do drzewa należy wykorzystać procedurę Wstaw, zdefiniowaną w procedurze Generuj_Drzewo. Aby to było możliwe należy przenieść procedurę Wstaw na poziom procedur globalnych.
9. Przetestować program, wykonując dostępne operacje w logicznej kolejności. Prześledzić postać drzewa utworzonego z wprowadzonych danych.
Zadania
1. Dla programu obsługi kartoteki w postaci drzewa rekordów, rozważ możliwość opracowania innych procedur np.
aktualizacji znalezionego rekordu,
usunięcia znalezionego rekordu,
przetwarzania danych z kartoteki w celu uzyskania dodatkowych wyników,
wygenerowania dokumentu dla wybranych rekordów z drzewa,
utworzenia wtórnego drzewa uporządkowanego wg. innego klucza, na podstawie pierwotnego drzewa,
pokazania drzewa rekordów w innej postaci graficznej np. od góry do dołu.
Dla kartoteki kont bankowych mogą to być procedury:
aktualizacji pola saldo, przy operacjach wpłaty i wypłaty,
usunięcia konta o podanym numerze,
obliczenia histogramu liczby kont, mieszczących się w różnych, zadanych przedziałach wartości,
utworzenia drzewa na podstawie klucza nazwisko_imie, lub nr_konta,
wygenerowania dokumentów informujących o powstaniu debetu na koncie, dla rekordów drzewa z ujemną wartością pola saldo.
Aktualizacja pola saldo może wymagać przemieszczenia zaktualizowanego rekordu w drzewie utworzonym wg. pola saldo, odpowiednio do aktualnej wartości pola.
Procedurę przekształcania drzewa utworzonego w oparciu o jeden klucz, na drzewo utworzone w oparciu o inny klucz może być zrealizowana:
bez zmian drzewa początkowego,
z kasowaniem drzewa początkowego.
W pierwszym przypadku dane są kopiowane do nowych węzłów, dołączanych do wtórnego drzewa, zaś w drugim węzły są odłączane z pierwotnego drzewa i dołączane do wtórnego drzewa.
2. Program obsługi kartoteki w postaci drzewa rekordów, uzupełnij o procedury określające pewne miary dla drzewa tj.
liczbę węzłów wewnętrznych,
liczbę węzłów zewnętrznych,
liczbę liści,
maksymalną długość ścieżki,
głębokość i wysokość określonego węzła,
długość drogi wewnętrznej,
długość drogi zewnętrznej.
3. Przy założeniu, że drzewo utworzone na podstawie kartoteki, zorganizowanej w pliku rekordów, nie zmieści się w całości w pamięci, utwórz drzewo indeksu do pliku, umożliwiające przyśpieszenie operacji wykonywanych na rekordach kartoteki. Zadeklaruj węzeł drzewa indeksu, zawierający klucz, wg. którego będzie odbywało się wyszukiwanie rekordów w kartotece, oraz numer rekordu w pliku. Napisz procedury obsługi kartoteki przy wykorzystaniu drzewa indeksu i pliku, tj. :
tworzenie drzewa odsyłaczy,
wyszukiwania rekordu w kartotece,
wybrania rekordów z kartoteki spełniających określony warunek,
usunięcia rekordu z kartoteki.
Jeżeli plik kartoteki istnieje, należy utworzyć drzewo indeksu na podstawie danych z pliku. Dla nowych rekordów wprowadzanych do pliku, należy tworzyć nowy węzeł i dołączać go do drzewa indeksu. Wyszukiwanie rekordu w kartotece ma znaleźć węzeł o poszukiwanym kluczu w drzewie indeksu, odczytać z niego numer rekordu w pliku i wykorzystując go odczytać rekord z pliku.
Wybieranie rekordów może korzystać z drzewa indeksu tylko wówczas, gdy dotyczy wybierania wg. pola klucza, wg. którego drzewo zostało utworzone. W tym celu należy przeglądać drzewo i odwoływać się tylko do wybranych z drzewa rekordów, przechowywanych w pliku. Przy wybieraniu wg. innego pola należy bezpośrednio przeglądać plik kartoteki. Usuwanie rekordu, o podanym kluczu z kartoteki, polega na usunięciu węzła, zawierającego ten klucz, z drzewa indeksu. Pomimo, że rekord pozostaje w pliku, brak usuniętego klucza w drzewie indeksu uniemożliwia dostęp do logicznie skasowanego rekordu. Okresowo należy jednak skompresować plik, przez przepisanie do innego pliku wyłącznie tych rekordów, których klucze znajdują się w drzewie indeksu, i utworzyć nowe drzewo indeksu na podstawie nowego pliku.
4. Przy założeniu , że drzewo kartoteki zorganizowanej w tablicy rekordów, pliku rekordów lub liście rekordów zmieści się w całości w pamięci, wykorzystać drzewo do posortowania kartoteki. W tym celu należy:
zdefiniować węzeł drzewa,
opracować procedury tworzenia drzewa na podstawie danych z nieposortowanej struktury, oraz przeglądania drzewa w kolejności in order, połączonego ze wstawianiem danych z węzła drzewa do posortowanej struktury danych,
oraz dołączyć je do programu obsługi kartoteki, opracowanego w ramach poprzednich ćwiczeń.
5. Przekształć drzewo rekordów w kopiec rekordów, o minimalnej wartości klucza w korzeniu, przyjmując zasadę, że na kolejnych poziomach wartości pola klucza są uporządkowane od lewej do prawej. W tym celu należy napisać procedurę przeglądającą drzewo w kolejności in order i dołączającą dane z przeglądanych węzłów do kopca, wypełniając kompletnie kolejne poziomy drzewa. Kolejny węzeł ma zostać dołączony na miejsce pierwszego napotkanego węzła zewnętrznego w kopcu, tj. węzła liścia jako lewy następnik, lub do węzła z jednym potomkiem jako prawy następnik.