Algorytmy i struktury danych - 05. ...

[ Pobierz całość w formacie PDF ]
Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne
1
Lekcja 5: Drzewa binarne
Wst
ħ
p
W tym rozdziale zajmiemy si
ħ
drzewami binarnymi, które s
Ģ
dynamicznymi strukturami rekurencyjnymi. Zamiast opisywa
ę
ich
sił
ħ
i mo
Ň
liwo
Ļ
ci - prezentujemy interesuj
Ģ
cy przykład zastosowania. To dla zach
ħ
ty, by
Ļ
cie polubili tworzenie struktur
drzewiastych.
Drzewo binarne
W Waszych programach niejednokrotnie zajdzie potrzeba zastosowania bardziej wyrafinowanych struktur danych ni
Ň
prosta lista.
Listy s
Ģ
znacznie bardziej elastyczne ni
Ň
tablice (poprzez dynamiczny sposób ich tworzenia), niestety s
Ģ
one tylko strukturami
liniowymi i przedstawienie zło
Ň
onych relacji mi
ħ
dzy obiektami przy u
Ň
yciu list jest mało wygodne. Struktur
Ģ
, któr
Ģ
zajmiemy si
ħ
w tym rozdziale, b
ħ
dzie
drzewo
(ang.
tree
). Tak jak lista jednokierunkowa jest najprostsz
Ģ
dynamiczn
Ģ
struktur
Ģ
liniow
Ģ
(jednowymiarow
Ģ
), tak drzewo jest dynamiczn
Ģ
struktur
Ģ
wielowymiarow
Ģ
. Drzewo jest regularn
Ģ
struktur
Ģ
danych składaj
Ģ
c
Ģ
si
ħ
z w
ħ
złów (odpowiednik elementów na li
Ļ
cie) posiadaj
Ģ
cych co najmniej dwa wska
Ņ
niki do takich samych w
ħ
złów. Tak, jak
prawdziwe drzewo w przyrodzie posiada liczne rozgał
ħ
zienia, tak samo i drzewo w informatyce posiada w
ħ
zły (wierzchołki) –
miejsca rozgał
ħ
zie
ı
. Ka
Ň
dy w
ħ
zeł mo
Ň
e wskazywa
ę
na kilka innych w
ħ
złów w drzewie. Jedynym w
ħ
złem, na którego nie
wskazuje
Ň
aden inny w
ħ
zeł drzewa, jest
korze
ı
. Natomiast w
ħ
zły, których wska
Ņ
niki s
Ģ
puste (czyli nie wskazuj
Ģ
na
Ň
aden inny
w
ħ
zeł), nazywamy najcz
ħĻ
ciej
li
Ļ
cmi
. Na ogół drzewa s
Ģ
przedstawiane w sposób graficzny z korzeniem na górze rysunku oraz z
li
Ļę
mi na dole. W
ħ
zły wskazywane przez dany w
ħ
zeł nazywamy jego
synami
(potomkami), natomiast on jest w stosunku dla nich
ojcem
. Najprostszym i zarazem najcz
ħĻ
ciej u
Ň
ywanym rodzajem drzewa jest
drzewo binarne
. Jest to struktura dwuwymiarowa.
W praktyce przejawia si
ħ
to tym,
Ň
e ka
Ň
dy element (w
ħ
zeł) ma dokładnie dwie odnogi - lew
Ģ
i praw
Ģ
(oczywi
Ļ
cie nie ka
Ň
da z nich
musi by
ę
wypełniona). Rysunek poni
Ň
ej pokazuje, jak takie drzewo mo
Ň
e wygl
Ģ
da
ę
.
2008-04-18 15:21
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne
2
Kolorem niebieskim oznaczyli
Ļ
my wska
Ņ
niki do innych w
ħ
złów drzewa.
ņ
eby uci
Ģę
w
Ģ
tpliwo
Ļ
ci – wska
Ņ
niki równe NULL/nil nie
s
Ģ
narysowane w postaci strzałek. Typowa definicja pojedynczego w
ħ
zła b
ħ
d
Ģ
cego składnikiem drzewa binarnego jest
nast
ħ
puj
Ģ
ca:
struct
Twezel {
int
Dane;
Twezel *Lewy;
Twezel *Prawy;
};
Ka
Ň
dy w
ħ
zeł zawiera pole do przechowywania informacji oraz dwa wska
Ņ
niki. Jak widzimy, wska
Ņ
niki w w
ħŅ
le zostały nazwane
mianem lewego oraz prawego – na ogół stosuje si
ħ
wła
Ļ
nie takie nazewnictwo, w którym w
ħ
zeł mo
Ň
e mie
ę
lewego oraz prawego
syna. Pami
ħ
tajmy,
Ň
e ka
Ň
dy w
ħ
zeł w drzewie binarnym nie musi mie
ę
obu synów – mo
Ň
e nie mie
ę
Ň
adnego, mo
Ň
e mie
ę
równie
Ň
jednego z synów (lewego lub prawego).
W tym miejscu nale
Ň
y wyja
Ļ
ni
ę
jedn
Ģ
niezmiernie istotn
Ģ
rzecz. Otó
Ň
, jak wiecie, lista dwukierunkowa składa si
ħ
z elementów
zawieraj
Ģ
cych dwa wska
Ņ
niki. Ró
Ň
nica mi
ħ
dzy tak
Ģ
list
Ģ
a drzewem kryje si
ħ
w sposobie poł
Ģ
czenia elementów. Elementy listy
dwukierunkowej pokazuj
Ģ
na siebie wzajemnie, tzn. je
Ļ
li drugi element listy wskazuje na trzeci, to trzeci wskazuje na drugi. Z
tego faktu wynika jeszcze jedno – ka
Ň
dy element listy z wyj
Ģ
tkiem pierwszego i ostatniego
musi
mie
ę
dwóch s
Ģ
siadów – czyli oba
wska
Ņ
niki w nim umieszczone s
Ģ
ró
Ň
ne od NULL/nil.
Natomiast przy drzewie binarnym zale
Ň
no
Ļę
ta nie jest spełniona. Po pierwsze: w
ħ
zeł mo
Ň
e mie
ę
jednego, dwu, lub nie mie
ę
wcale synów. Po drugie: je
Ļ
li A wskazuje na B, to B
nie mo
Ň
e
wskazywa
ę
na A.
Drzewa binarnego wyszukiwania
Drzewa binarne mog
Ģ
by
ę
tworzone według ró
Ň
nych reguł. Jedn
Ģ
z grup drzew binarnych, na której s
Ģ
okre
Ļ
lone reguły
zachowywania si
ħ
elementów w drzewie s
Ģ
drzewa binarnego przeszukiwania (ang.
Binary Search Tree
-
BST
). Struktura BST
jest stosowana przede wszystkim w celu szybkiego wyszukiwania danych (a tak
Ň
e dodawania i usuwania informacji); cz
ħ
sto przy
u
Ň
yciu takich drzew realizowane s
Ģ
struktury słownikowe oraz kolejki priorytetowe, które dopiero poznacie. Główna zasada
istniej
Ģ
ca w drzewie BST jest taka,
Ň
e warto
Ļ
ci w w
ħ
złach znajduj
Ģ
cych si
ħ
„na lewo” od danego w
ħ
zła s
Ģ
mniejsze ni
Ň
warto
Ļę
zapisana w tym w
ħŅ
le, natomiast wszystkie warto
Ļ
ci w w
ħ
złach znajduj
Ģ
cych si
ħ
„na prawo” od danego w
ħ
zła s
Ģ
wi
ħ
ksze ni
Ň
warto
Ļę
w nim zapisana. Mówi
Ģ
c
Ļ
cisłej, warto
Ļę
w w
ħŅ
le jest wi
ħ
ksza ni
Ň
warto
Ļ
ci w w
ħ
złach znajduj
Ģ
cych si
ħ
w lewym
poddrzewie
(czyli drzewie o korzeniu b
ħ
d
Ģ
cym jego lewym synem), natomiast warto
Ļę
w konkretnym w
ħŅ
le jest mniejsza ni
Ň
warto
Ļ
ci w w
ħ
złach znajduj
Ģ
cych si
ħ
w prawym poddrzewie. Zatem:
wszystkie warto
Ļ
ci lewego poddrzewa < warto
Ļę
w w
ħŅ
le < wszystkie warto
Ļ
ci prawego poddrzewa
Ta zale
Ň
no
Ļę
obowi
Ģ
zuje na ka
Ň
dym poziomie drzewa BST, a wi
ħ
c zarówno dla jego korzenia, jak i dla wszystkich poddrzew
dowolnego w
ħ
zła. Mo
Ň
ecie to sprawdzi
ę
na poni
Ň
szej animacji i na wszystkich nast
ħ
pnych rysunkach w tej lekcji.
2008-04-18 15:21
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne
3
Struktura BST wymaga, by ka
Ň
dy w
ħ
zeł posiadał unikatow
Ģ
warto
Ļę
danej - to bardzo wa
Ň
ne:
elementy drzewa BST nie mog
Ģ
si
ħ
powtarza
ę
!.
Przyjrzyjcie si
ħ
, jak działa proces tworzenia drzewa BST:
Skoro pokazali
Ļ
my w sposób graficzny, jak dodawane s
Ģ
nowe elementy do drzewa BST, to równie
Ň
warto przedstawi
ę
Ļ
cisły kod
budowania takiego drzewa. Kod realizuj
Ģ
cy dodawanie nowego w
ħ
zła mo
Ň
na przedstawi
ę
w postaci procedury rekurencyjnej (z
przekazywaniem referencji do wska
Ņ
nika), wraz z przykładowym jej wywołaniem w programie:
void
DodajWezel (Twezel *&wezel,
int
wartosc) {
if
(wezel == NULL) {
// tworzymy i doł
Ģ
czamy element
wezel =
new
Twezel;
wezel -> Dane = wartosc;
wezel -> Lewy = NULL;
wezel -> Prawy = NULL;
}
else
if
(wartosc < wezel -> Dane) DodajWezel (wezel -> lewy, wartosc );
// rekurencyjne wywo
else
if
(wartosc > wezel -> Dane) DodajWezel (wezel -> prawy, wartosc );
// rekurencyjne wywola
// uwaga: liczby powtarzaj
Ģ
ce si
ħ
nie s
Ģ
dodawane do drzewa
}
int
main( ) {
int
n, liczba;
Twezel korzen;
korzen=NULL;
cin >> n;
// załó
Ň
my,
Ň
e n liczb ma by
ę
wczytanych
for
(
int
i=0; i<n; i++) {
cin >> liczba;
DodajWezel (korzen, liczba);
// teraz korzen nie jest ju
Ň
NULL
...
}
}
Algorytm dodawania w
ħ
zła w sposób rekurencyjny wykonuje si
ħ
si
ħ
od korzenia w stron
ħ
li
Ļ
ci, poruszaj
Ģ
c si
ħ
w lewo b
Ģ
d
Ņ
w
prawo w zale
Ň
no
Ļ
ci od wyniku porównania z napotkanymi w
ħ
złami. W momencie dotarcia do jednego z li
Ļ
ci nast
ħ
puje ostatnie
porównanie warto
Ļ
ci, po czym nowy w
ħ
zeł staje si
ħ
lewym lub prawym synem w
ħ
zła, który do tego czasu był li
Ļ
ciem. Zło
Ň
ono
Ļę
czasowa algorytmu
DodajWezel
jest rz
ħ
du
O(h)
, gdzie h jest
wysoko
Ļ
ci
Ģ
drzewa. Dopiero teraz wprowadzamy poj
ħ
cie wysoko
Ļ
ci
– oznacza ona odległo
Ļę
korzenia (w sensie liczby kraw
ħ
dzi) od najbardziej oddalonego li
Ļ
cia drzewa.
Warto w tym miejscu pokaza
ę
na rysunkach, w jaki sposób dodawany w
ħ
zeł w
ħ
druje w od korzenia w stron
ħ
li
Ļ
ci w poszukiwaniu
odpowiedniego miejsca dla siebie.
2008-04-18 15:21
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne
4
Przykładowo, chcemy wczyta
ę
ci
Ģ
g liczb 5, 3, 8, 2, 6, 4, 9, 1, 7, które s
Ģ
warto
Ļ
ciami zapisywanymi w w
ħ
złach. Po utworzeniu
drzewa BST z liczb 5, 3, 8, 2, 6, 4, 9 prezentujemy poni
Ň
ej dodanie w
ħ
zła o warto
Ļ
ci 1:
Z kolei w nast
ħ
pnym (ostatnim) kroku dodawany jest w
ħ
zeł o warto
Ļ
ci 7:
Skoro wiemy ju
Ň
, w jaki sposób tworzy si
ħ
drzewo BST, warto by było pozna
ę
korzy
Ļ
ci płyn
Ģ
ce z u
Ň
ywania takiej struktury
danych. Jedna z nich zawarta jest w procedurach wy
Ļ
wietlania drzewa BST. Otó
Ň
omawiane drzewo mo
Ň
na wy
Ļ
wietli
ę
na 3
główne sposoby:
w kolejno
Ļ
ci
inorder
: najpierw lewe poddrzewo, potem w
ħ
zeł, a nast
ħ
pnie prawe poddrzewo
w kolejno
Ļ
ci
preorder
: najpierw w
ħ
zeł, potem lewe poddrzewo, a nast
ħ
pnie prawe poddrzewo
w kolejno
Ļ
ci
postorder
: najpierw lewe poddrzewo, potem prawe poddrzewo, a na samy ko
ı
cu w
ħ
zeł
Powy
Ň
sze sposoby tak naprawd
ħ
dotycz
Ģ
metod przechodzenia przez drzewo i kolejno
Ļ
ci odwiedzania jego wierzchołków – przy
okazji „odwiedzin” mo
Ň
emy wy
Ļ
wietli
ę
zawarto
Ļę
tego w
ħ
zła.
Co ciekawe, jeden z tych sposobów zwiedzania wierzchołków daje w rezultacie wy
Ļ
wietlanie zawarto
Ļ
ci w
ħ
złów w kolejno
Ļ
ci
posortowanej (rosn
Ģ
cej). Chodzi konkretnie o metod
ħ
inorder
.
void
WyswietlDrzewo (Twezel *wezel) {
// porz
Ģ
dek inorder
if
(wezel != NULL) {
WyswietlDrzewo (wezel->Lewy);
// lewe poddrzewo
cout << wezel->Dane <<
" "
;
// w
ħ
zeł
WyswietlDrzewo (wezel->Prawy);
// prawe poddrzewo
}
}
Odnosz
Ģ
c si
ħ
do naszego przykładowego drzewa, liczby zapisane w w
ħ
złach zostan
Ģ
wy
Ļ
wietlone w kolejno
Ļ
ci:
1, 2, 3, 4, 5, 6, 7,
8, 9.
2008-04-18 15:21
 Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne
5
Odczytanie danych w kolejno
Ļ
ci
inorder
wymaga rekurencyjnego si
ħ
gania w pierwszej kolejno
Ļ
ci do skrajnie lewych w
ħ
złów
drzewa, nast
ħ
pnie w razie konieczno
Ļ
ci cofamy si
ħ
o jeden poziom, odczytujemy warto
Ļę
w
ħ
zła, przechodzimy do jego prawego
syna i ponownie próbujemy pod
ĢŇ
a
ę
skrajnie na lewo. Algorytm wykonuje si
ħ
do momentu odwiedzenia wszystkich w
ħ
złów
drzewa. Zauwa
Ň
cie,
Ň
e warto
Ļę
w
ħ
zła jest odczytywana dopiero przy jego drugich "odwiedzinach", jak ju
Ň
nie mo
Ň
emy i
Ļę
dalej
w lewo. Ta kolejno
Ļę
odczytywania elementów wynika z kolejno
Ļ
ci rekurencyjnych wywoła
ı
w procedurze powy
Ň
ej i mo
Ň
ecie
prze
Ļ
ledzi
ę
j
Ģ
na poni
Ň
szym rysunku, gdzie czerwon
Ģ
lini
Ģ
zaznaczona została droga poruszania si
ħ
wzdłu
Ň
drzewa w trakcie tych
wywoła
ı
. Zielone kółeczka oznaczaj
Ģ
miejsca odczytu w
ħ
złów, czerwone numerki przy nich to numer kolejny odczytywanego
w
ħ
zła.
Mamy wi
ħ
c prosty sposób sortowania danych:
wpisa
ę
je do drzewa BST, a nast
ħ
pnie odczyta
ę
w kolejno
Ļ
ci inorder.
Mo
Ň
ecie to teraz dokładnie prze
Ļ
ledzi
ę
na ró
Ň
nych przykładach drzew, korzystaj
Ģ
c ze specjalnie napisanego w tym celu apletu -
wejdziecie do niego klikaj
Ģ
c w poni
Ň
szy obrazek. Autor tego ciekawego apletu przygotował go dla Was w postaci tradycyjnego
drzewa, rosn
Ģ
cego od dołu do góry - ale zauwa
Ň
cie,
Ň
e spełnia ono nadal wszystkie warunki drzewa BST, warto
Ļ
ci w lewym
poddrzewie s
Ģ
mniejsze ni
Ň
w prawym itd. Tradycyjne drzewo binarne (rosn
Ģ
ce do dołu) mo
Ň
na z niego otrzyma
ę
przez odbicie
lustrzane wzgl
ħ
dem poziomej linii u podnó
Ň
a drzewa, nie za
Ļ
przez obrót.
Dla porównania przedstawimy równie
Ň
kod programu oraz schemat rysunkowy dla metod preorder oraz postorder.
2008-04-18 15:21
[ Pobierz całość w formacie PDF ]