BINARNE DRZEWA POSZUKIWAŃ
Na podstawie: N. Wirth, „Algorytmy + struktury danych =programy”, WNT,
Eleganckim i efektywnym sposobem definiowania bardziej złożonych struktur
danych jest rekurencja. Zdefiniujmy zatem strukturę drzewiastą następująco:
Struktura drzewiasta o typie podstawowym T jest albo
1) Strukturą pustą, albo
2) Węzłem typu T ze skończoną liczbą dowiązanych rozłącznych struktur
drzewiastych o typie podstawowym T, nazywanych poddrzewami.
Przykłady drzew:
· Struktura plików systemu operacyjnego
· Książka, rozdziały, podrozdziały, sekcje, paragrafy, itd.
· Drzewo genealogiczne
· Menu telefonu komórkowego
· Drzewo opisujące wyrażenie arytmetyczne
Reprezentacja drzew
Jest wiele sposobów reprezentacji struktur drzewiastych. Na przykład niech
typ podstawowy T obejmuje litery; odpowiednia struktura jest przedstawiona
na kilka sposobów na rys. 1. Wszystkie reprezentacje mają taką samą strukturę
i dlatego są równoważne. Spośród nich graf najwyraźniej ilustruje relacje
powiązań. Charakter tych powiązań uzasadnia wybór nazwy struktury -
„drzewo". Rzecz dziwna, zwykle rysuje się drzewo odwrócone lub - wyrażając ten fakt inaczej - uwidacznia się korzenie drzewa.
- 1 -
Rysunek 1
- 2 -
Korzeniem drzewa nazywamy zwykle najwyższy węzeł (A). Drzewem
uporządkowanym jest drzewo, w którym gałęzie każdego węzła są
uporządkowane. Węzeł y, który znajduje się bezpośrednio poniżej węzła x, nazywamy (bezpośrednim) potomkiem x. Jeżeli x znajduje się na poziomie i, to mówimy, że y znajduje się na poziomie i + 1. I odwrotnie, węzeł x nazywany (bezpośrednim) przodkiem y. Poziom korzenia drzewa
definiujemy jako 1. Maksymalny poziom wszystkich elementów drzewa
nazywamy jego głębokością lub wysokością. Element nie mający
potomków nazywamy elementem końcowym lub liściem. Element nie
będący liściem nazywamy węzłem wewnętrznym. Liczbę (bezpośrednich)
potomków wewnętrznego węzła nazywamy jego stopniem. Maksymalny
stopień wszystkich węzłów jest stopniem drzewa. Liczbę gałęzi lub krawędzi,
przez które należy przejść od korzenia do węzła x, nazywamy długością ścieżki (lub drogi) x. Długość ścieżki korzenia jest równa 1, jego bezpośredni potomek ma długość ścieżki równą 2 itd. Ogólnie, długość ścieżki węzła na
poziomie i jest równa i. Długość ścieżki drzewa definiujemy jako sumę długości
ścieżek wszystkich jego składowych. Nazywamy ją także długością ścieżki
wewnętrznej. Na przykład długość ścieżki wewnętrznej drzewa z rys. 1 równa
jest 52.
Drzewo jest doskonale zrównoważone (dokładnie wyważone), jeżeli dla
każdego węzła liczby węzłów w jego lewym i prawym poddrzewie różnią się co
najwyżej o 1.
- 3 -
Drzewa binarne
Drzewa uporządkowane o stopniu 2 okazują się szczególnie ważne. Nazywane
są drzewami binarnymi. Uporządkowane drzewo binarne definiujemy jako
skończony zbiór elementów (węzłów), który jest albo pusty, albo zawiera
korzeń (węzeł) z dwoma rozłącznymi binarnymi drzewami zwanymi lewym
i prawym poddrzewem korzenia.
Każdy węzeł ma co najwyżej 2 następniki, które potocznie nazywane są
„lewym” i „prawym”. Dodatkowo, jeśli wiadomo, że dla każdego węzła ti
wszystkie klucze z lewego poddrzewa węzła ti są mniejsze od klucza węzła ti, a klucze z prawego poddrzewa są od niego większe, to mamy do czynienia
wtedy z drzewem poszukiwań. W drzewie takim można znaleźć określony
klucz, posuwając się wzdłuż ścieżki poszukiwania – począwszy od korzenia –
i przechodząc do lewego lub prawego poddrzewa danego węzła w zależności
tylko od wartości klucza w tym węźle.
Rysunek 2
Drzewo w swym korzeniu ma wartość 10. Zauważmy, że wszystkie wartości
leżące na jego lewych gałązkach są od 10 mniejsze, a na prawych większe.
Możemy przyjrzeć się np. poddrzewu o wartości korzenia 7. Znów sytuacja się
powtarza - wszystko, co po lewej stronie jest mniejsze, a to co po prawej -
większe.
- 4 -
Przeglądanie drzewa
Czynnością powszechnie wykonywaną na strukturze drzewiastej jest
odwiedzanie wszystkich węzłów, nazywane zwykle przeglądaniem drzewa
(przechodzeniem drzewa). Jeśli rozważymy to zadanie jako proces
sekwencyjny, to odwiedzanie pojedynczych węzłów odbywa się w pewnym
porządku i można uważać, że węzły zostały ułożone wzdłuż linii.
Istnieją trzy podstawowe uporządkowania wynikające w sposób naturalny ze
struktury drzew. Podobnie jak samą strukturę drzewiastą można je zręcznie
wyrazić za pomocą pojęć rekurencyjnych. Powołując się na drzewo binarne z
rys. 3, w którym K oznacza korzeń, A i B zaś – lewe i prawe poddrzewa,
wyróżniamy trzy porządki:
1) preorder (wzdłużny): K, A, B (odwiedzamy korzeń przed poddrzewami); 2) inorder (poprzeczny): A, K, B;
3) postorder (wsteczny): A, B, K (odwiedzamy korzeń po poddrzewach).
Rysunek 3
- 5 -
Przyjmujemy następujące definicje typów danych:
type
wsk = ^wezel;
wezel = record
klucz : integer;
licznik : integer;
lewe, prawe : wsk;
end;
Procedura Drukowanie odpowiada za wydruk powstałego drzewa na ekranie.
Zastosowano metodę inorder, dzięki czemu wydrukowane elementy są
uporządkowane rosnąco.
procedure Drukowanie (w : wsk; l : integer);
var
i : integer;
begin
if w <> nil then
with w^ do
begin
Drukowanie (lewe, l+1);
for i := 1 to l do
write (' ');
writeln (klucz);
Drukowanie (prawe, l+1);
end
end;
Procedura Szukaj_i_Wstaw szuka w drzewie elementu x, jeśli taki element
się znajduje, wtedy zwiększa licznik o 1, a jeśli nie, wtedy element jest
dodawany do drzewa.
Poczynając od pustego drzewa, szukamy w drzewie danego słowa. Po jego
znalezieniu zwiększa się licznik wystąpień. W przeciwnym razie jest ono
wstawiane jako nowe słowo (z licznikiem równym 1). Rozważmy na przykład
drzewo binarne z rys. 4 i wstawienie słowa „Paweł”. Wynik oznaczono liniami
przerywanymi na tym samym rysunku.
- 6 -
Rysunek 4
Proces przeszukiwania jest sformułowany w postaci procedury rekurencyjnej.
Zwróćmy uwagę, że parametr p jest przekazywany przez zmienną, a nie przez
wartość. Jest to istotne, gdyż przy wstawianiu zmiennej mającej uprzednio
wartość nil musi być przypisana nowa wartość wskaźnika.
Korzystając z ciągu wejściowych 21 liczb:
8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18
program daje w wyniku drzewo binarne pokazane na rys. 5.
- 7 -
Rysunek 5
procedure Szukaj_i_Wstaw (x : integer; var p : wsk);
begin
if p = nil then
begin
new (p);
with p^ do
begin
klucz := x;
licznik := 1;
lewe := nil;
prawe := nil;
end;
writeln ('Elementu nie bylo w drzewie. Wstawiono nowy wezel.');
end
else
if x < p^.klucz then
Szukaj_i_Wstaw (x, p^.lewe)
else if x > p^.klucz then
Szukaj_i_Wstaw (x, p^.prawe)
else
begin
p^.licznik := p^.licznik + 1;
writeln ('Element zjadowal sie w drzewie. Zwiekszono licznik o 1.');
end;
end;
- 8 -
Przejdźmy teraz do problemu odwrotnego względem wstawiania, tj. do usuwania. Zadaniem naszym jest zdefiniowanie algorytmu usuwania węzła o
kluczu x z drzewa z uporządkowanymi kluczami. Niestety, usunięcie elementu
nie jest na ogół takie proste jak wstawienie. Jest to łatwa operacja wtedy, gdy
usuwany element jest węzłem końcowym lub ma tylko jednego potomka.
Trudności pojawiają się przy usuwaniu elementu mającego dwóch potomków,
ponieważ jednym wskaźnikiem nie możemy wskazać dwóch kierunków. W tej
sytuacji usuwany element musi być zastąpiony przez skrajny prawy element
lewego poddrzewa lub skrajny lewy węzeł prawego poddrzewa, z których każdy
ma co najwyżej jednego potomka. Szczegóły algorytmu są zawarte w
rekurencyjnej procedurze Usuń. Rozróżnia się w niej trzy przypadki:
1) Brak składowej o kluczu równym x.
2) Składowa o kluczu x ma co najwyżej jednego potomka.
3) Składowa o kluczu x ma dwóch potomków.
Pomocnicza procedura rekurencyjna Us jest wywoływana tylko w trzecim
przypadku. „Schodzi” ona wzdłuż skrajnej prawej krawędzi lewego poddrzewa
elementu q^, który należy usunąć, a następnie wymienia związaną z q^
informację (klucz i licznik) na odpowiadające wartości skrajnie prawego
składnika r^ lewego poddrzewa, po czym r^ może być zwolniony.
Aby zilustrować funkcjonowanie procedury, odwołamy się do rys. 6. Mamy
dane drzewo (a), następnie usuwamy kolejno węzły o kluczach 13, 15, 5, 10.
Drzewo powstałe w wyniku tej operacji pokazano na rysunku.
- 9 -
Rysunek 6
procedure Usun (x : integer; var p : wsk);
var
q : wsk;
procedure Us (var r : wsk); { Procedura pomocnicza Us }
begin
if r^.prawe <> nil then
Us (r^.prawe)
else
begin
q^.klucz := r^.klucz;
q^.licznik := r^.licznik;
q:= r;
r:= r^.lewe;
end;
end; {--- Us -}
begin
if p = nil then
writeln ('Brak slowa w drzewie.')
else
if x < p^.klucz then
Usun (x, p^.lewe)
else
if x > p^.klucz then
Usun (x, p^.prawe)
else
begin { Usun p^ }
q := p;
if q^.prawe = nil then
p := q^.lewe
else
if q^.lewe = nil then
p := q^.prawe
else Us (q^.lewe);
end
end;
- 10 -
program Drzewo_Binarne;
q^.licznik := r^.licznik;
q:= r;
uses
r:= r^.lewe;
Crt;
end;
end; {--- Us -}
type
wsk = ^wezel;
begin
wezel = record
if p = nil then
klucz : integer;
writeln ('Brak slowa w drzewie.')
licznik : integer;
else
lewe, prawe : wsk;
if x < p^.klucz then
end;
Usun (x, p^.lewe)
else
var
if x > p^.klucz then
korzen : wsk;
Usun (x, p^.prawe)
k : integer;
else
co : char;
begin { Usun p^ }
q := p;
if q^.prawe = nil then
procedure Drukowanie (w : wsk; l : integer);
p := q^.lewe
var
else
i : integer;
if q^.lewe = nil then
begin
p := q^.prawe
if w <> nil then
else Us (q^.lewe);
with w^ do
end
begin
end; {--- Usun -}
Drukowanie (lewe, l+1);
for i := 1 to l do
write (' ');
begin { Main }
writeln (klucz);
Drukowanie (prawe, l+1);
korzen := nil; { Utworzenie pustego drzewa }
end
end; {--- Drukowanie -}
repeat
ClrScr;
procedure Szukaj_i_Wstaw (x : integer; var p : wsk);
writeln ('Wybierz operacje: ');
{ Procedura szuka w drzewie elementu x, jesli taki element sie
writeln ('1 - Drukowanie drzewa');
znajduje, }
writeln ('2 - Szukaj i Wstaw');
{ wtedy zwieksza licznik o 1, a jesli nie, wtedy elemet jest dodawany
writeln ('3 - Usun z drzewa');
do drzewa }
writeln ('4 - Aktualizacja');
begin
writeln;
if p = nil then
writeln ('0 - Koniec programu');
begin
writeln;
new (p);
with p^ do
co := readkey;
begin
klucz := x;
case co of
licznik := 1;
'1' : begin
lewe := nil;
Drukowanie (korzen, 3);
prawe := nil;
write ('Nacisnij Enter, aby kontynuowac');
end;
readln;
writeln ('Elementu nie bylo w drzewie. Wstawiono nowy
end;
wezel.');
'2' : begin
end
write ('Podaj wartosc k: ');
else
readln (k);
if x < p^.klucz then
Szukaj_i_Wstaw (k, korzen);
Szukaj_i_Wstaw (x, p^.lewe)
write ('Nacisnij Enter,
else if x > p^.klucz then
aby kontynuowac');
Szukaj_i_Wstaw (x, p^.prawe)
readln;
else
end;
begin
'3' : begin
p^.licznik := p^.licznik + 1;
write ('Podaj wartosc k: ');
writeln ('Element zjadowal sie w drzewie. Zwiekszono licznik
readln (k);
o 1.');
Usun (k, korzen);
end;
end;
end; {--- Szukaj_i_Wstaw -}
'4' : begin
write ('Podaj stara wartosc: ');
readln (k);
procedure Usun (x : integer; var p : wsk);
Usun (k, korzen);
var
write ('Podaj nowa wartosc: ');
q : wsk;
readln (k);
Szukaj_i_Wstaw (k, korzen);
procedure Us (var r : wsk); { Procedura pomocnicza Us }
end;
begin
end;
if r^.prawe <> nil then
until co = '0';
Us (r^.prawe)
end. {--- Main -}
else
begin
q^.klucz := r^.klucz;
- 11 -