Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Struktury danych
1.1 Listy, stosy i kolejki
Lista to uporzadkowany ciag elementów. Przykładami list sa wektory lub tablice jednowy-
¸ ¸ ¸
miarowe. W wektorach mamy dostep do dowolnego elementu, poprzez podanie indeksu
¸
tego elementu.
Przykład 1.1 W jezyku Pascal przykładem typu tablicy jednowymiarowej jest
¸
array[1..N] of integer.
Jeżeli mamy zmienna tego typu
¸
a:array[1..N] of integer,
to tablicaazawieraNelementów
a[1], a[2], ... ,a[N].
W programie możemy odwoływać sie do całej tablicy, na przykład w instrukcji przypisania
¸
a:=b,
lub do pojedynczych elementów:
a[i]:=a[i+1].
Możemy także używać tablic dwu lub wiecej wymiarowych. Przykładem tablicy dwuwy-
¸
miarowej jest typ
array[1..N,1..M] of real.
Zmienna
c:array[1..N,1..M] of real

zawiera elementów. Dla każdej pary liczb spełniajacej warunki ,
¸

¸
, elementc[i,j]zawiera liczbe typureal.
Czasami wygodniej posługiwać sie listami bez używania indeksów. Przykładami list,
¸
których można używać bez konieczności odwoływania sie do indeksów poszczególnych
¸
elementów, sa kolejki i stosy.
¸
3
4 Rozdział 1. Struktury danych
Definicja 1.2 Kolejka jest lista z trzema operacjami:
¸

dodawania nowego elementu na koniec kolejki,

zdejmowania pierwszego elementu z poczatku kolejki,
¸

sprawdzania, czy kolejka jest pusta.
Taki sposób dodawania i odejmowania elementów jest określany angielskim skrótem
FIFO (first in first out, czyli pierwszy wszedł  pierwszy wyjdzie). Przykłady kolejek
spotykamy w sklepach, gdzie klienci czekajacy na obsłużenie tworza kolejki.
¸ ¸
Definicja 1.3 Stos jest lista z trzema operacjami:
¸

dodawania elementu na wierzch stosu,

zdejmowania elementu z wierzchu stosu,

sprawdzania, czy stos jest pusty.
Na stosie dodajemy i odejmujemy elementy z tego samego końca, podobnie jak w
stosie talerzy spietrzonym na stole. Talerze dokładane sa na wierzch stosu i zdejmowa-
¸ ¸
ne z wierzchu stosu. Taka organizacja obsługi listy określana jest angielskim skrótem
LIFO (last in first out, czyli ostatni wszedł  pierwszy wyjdzie). Niektórzy w ten spo-
sób organizuja prace na biurku. Przychodzace listy układaja na stosie i jak maja czas, to
¸ ¸ ¸ ¸ ¸
zdejmuja jeden list i odpowiadaja na niego.
¸ ¸
Przyjrzyjmy sie zastosowaniu kolejki lub stosu do szukania. Przypuśćmy, że szukamy
¸
przez telefon pewnej informacji (na przykład chcielibyśmy sie dowiedzieć, kto z naszych
¸
znajomych ma pewna ksiażke).
¸ ¸ ¸
Algorytm szukania ksiażki wśród znajomych
¸

tworzymy STOS, który na poczatku jest pusty,
¸

wkładamy na STOS numer telefonu swojego znajomego,

powtarzamy dopóki na stosie sa jakieś numery:
¸

zdejmujemy z wierzchu STOSU jeden numer telefonu,

dzwonimy pod ten numer,

jeżeli osoba, do której sie dodzwoniliśmy, posiada szukana ksiażke, to ko-
¸ ¸ ¸ ¸
niec poszukiwań,

jeżeli nie posiada ksiażki, to pytamy ja o numery telefonów jej znajomych,
¸ ¸
którzy moga mieć ksiażke (lub znać kogoś kto ja ma); każdy nowy numer zostaje
¸ ¸ ¸ ¸
dopisany do STOSU.
W powyższym algorytmie zamiast stosu może być użyta kolejka.
1.2. Drzewa binarne 5
1.2 Drzewa binarne
Drzewo jest hierarchiczna struktura danych. Jeden element drzewa, zwany korzeniem, jest
¸ ¸
wyróżniony. Inne elementy drzewa sa jego potomstwem lub potomstwem jego potomstwa
¸
itd. Terminologia używana do opisu drzew jest mieszanina terminów z teorii grafów, bo-
¸
taniki i stosunków rodzinnych. Elementy drzewa nazywa sie wierzchoÅ‚kami lub w¸
¸ ezÅ‚ami.
Liście to wierzchołki nie majace potomstwa. Drzewa czesto przedstawia sie w formie
¸ ¸ ¸
grafu, gdzie każdy wierzchoÅ‚ek jest poÅ‚aczony kraw¸ ¸ ze swoim ojcem i ze swoimi
¸ edzia
dziećmi (swoim potomstwem). Dla każdego elementu w drzewie istnieje dokładnie jedna
ścieżka prowadzaca od korzenia do tego wierzchołka.
¸
Drzewa binarne to takie drzewa, w których każdy wierzchołek ma co najwyżej dwóch
synów. Do oznaczania wierzchołków w drzewie binarnym wygodnie jest używać ciagów
¸

¸
zer i jedynek. Niech oznacza zbiór wszystkich skończonych ciagów zer i jedy-
nek. Zbiór ten zawiera ciag pusty (długości 0), oznaczany przez . Wierzchołki drzewa
¸
oznaczamy w nastepujacy sposób:
¸ ¸

korzeń drzewa oznaczamy przez  pusty ciag,
¸

je jakiś wierzchołek jest oznaczony przez , to jego synowie oznaczeni sa przez
żeli ¸
i .
Rysunek 1.1: Przykład drzewa binarnego







Przy takim oznaczeniu wierzchołków drzewa binarnego nazwa wierzchołka mówi
nam, jaka ścieżka prowadzi od korzenia do . Na przykład, aby dojść od korzenia do

wierzchołka nalezy: pójść w prawo do , potem znowu w prawo do , a na końcu w

lewo do .
6 Rozdział 1. Struktury danych
Jeżeli mamy drzewo binarne , to z każdym wierzchołkiem możemy skojarzyć
poddrzewo złożone z wierzchołka i wszystkich jego potomków. Na przykład w
drzewie przedstawionym na rysunku 1.1 wierzchołek wyznacza poddrzewo

przedstawione na rysunku 1.2.
Rysunek 1.2: Poddrzewo





Mówimy też, że drzewo składa sie z korzenia (wierzchołka ), z lewego poddrzewa
¸
i z prawego poddrzewa .
Wysokościa drzewa nazywamy długość (liczbę krawędzi) najdłuższej ścieżki w drze-
¸
wie prowadzacej od korzenia do liścia. Na przykład drzewo z rysunku 1.1 jest wysokości
¸
3.
1.3 Drzewa wyrażeń arytmetycznych
Przykładem zastosowania drzew binarnych sa drzewa wyrażeń arytmetycznych. Najpierw
¸
przykład. Na rysunku 1.3 przedstawiono drzewo wyrażenia . W drzewie tym każ-
dy wierzchołek ma etykiete. Liście etykietowane sa stałymi albo zmiennymi. Wierzchołki
¸ ¸
nie bedace liśćmi etykietowane sa operacjami arytmetyczymi. Każdemu wierzchołkowi
¸ ¸ ¸
w drzewie możemy przypisać wyrażenie arytmetyczne według nastepujacej zasady:
¸ ¸

dla liści wyrażeniami sa etykiety tych liści (stałe lub zmienne),
¸



jeżeli wierzchołek ma etykiete , a jego synom przypisano wyrażenia i
¸


, to wierzchołkowi przypisujemy wyrażenie .

Przykład 1.4 W drzewie z rysunku1.3 wierzchołkowi z etykietą odpowiada wyrażenie

, wierzchołkowi z etykietą wyrażenie , a korzeniowi wyrażenie



Wyrażenie to zawiera wiecej nawiasów, niż to sie zwykle stosuje. Normalnie to samo wy-
¸ ¸
rażenie przedstawiamy bez nawiasów w postaci .
1.3. Drzewa wyrażeń arytmetycznych 7
Rysunek 1.3: Drzewo wyrażenia




Opuszczenie nawiasów może prowadzić do niejednoznaczności lub może zmienić
sens wyrażenia. Na przykład wyrażenie


po opuszczeniu nawiasów stanie sie identyczne z wyrażeniem i zmieni sens.
¸
Drzewo, które odpowiada wyrażeniu , przedstawiono na rysunku 1.4.

Rysunek 1.4: Drzewo wyrażenia




Drzewo wyrażenia arytmetycznego oddaje logiczna strukture i sposób obliczania tego
¸ ¸
wyrażenia.
8 Rozdział 1. Struktury danych
Istnieje sposób przedstawiania wyrażeń arytmetycznych nie wymagajacy nawiasów.
¸
Jest to tak zwana notacja polska lub A
ukasiewicza. Jest ona też nazywana notacja postfixow¸
¸ a,
ponieważ znak operacji stoi na końcu wyrażenia, za argumentami, czyli wyrażenie w no-
tacji postfixowej ma postać:
pierwszy argument  drugi argument  operacja.
Notacja, do jakiej jesteśmy przyzwyczajeni, nazywa sie infixowa, ponieważ operacja znaj-
¸
duje sie pomiedzy argumentami, czyli wyrażenie w notacji infixowej ma postać:
¸ ¸
pierwszy argument  operacja  drugi argument.
Przykład 1.5 Wyrażenie w postaci postfixowej


ma w postaci infixowej postać

a wyrażenie



jest postfixowa postacia wyrażenia
¸ ¸


W wyrażeniach w postaci postfixowej nie potrzeba nawiasów. Wartość wyrażenia można
w sposób jednoznaczny odtworzyć z samego wyrażenia za pomoca następującego algo-
¸
rytmu.:
Algorytm obliczania wartości wyrażenia w postaci postfixowej.
Dla kolejnych elementów zapisu wyrażenia:

jeżeli element jest stała lub zmienna, to wkładamy jego wartość na stos,
¸ ¸

jeżeli element jest znakiem operacji, to:

zdejmujemy dwie wartości z wierzchu stosu,

wykonujemy operacje na tych wartościach,
¸

obliczona wartość wkładamy na wierzch stosu,
¸

po przejściu całego wyrażenia jego wartość znajduje sie na stosie.
¸
Przykład 1.6 Zademonstrujmy ten algorytm na przykładzie wyrażenia:




Załóżmy, że zmienne maja nastepujace wartości: , , , , .
¸ ¸ ¸
Poniższa tabela przedstawia zawartość stosu po przeczytaniu kolejnych elementów wyra-
żenia.
1.4. Przeszukiwanie drzew binarnych 9
czytany element stos
a 3,
b 3, 2,
c 3, 2, 1,
3, 3,

9,
d 9, 4,
e 9, 4, 2,
9, 2,
11.
1.4 Przeszukiwanie drzew binarnych
Zajmiemy sie teraz dwoma algorytmami przeszukiwania drzew (binarnych): przeszuki-
¸
wanie w głab i wszerz. Różnia sie one rodzajem użytych struktur danych. W algorytmie
¸ ¸ ¸
przeszukiwania w głab użyjemy stosu, a w algorytmie przeszukiwania wszerz użyjemy
¸
kolejki.
1.4.1 Przeszukiwanie drzewa w głąb
Algorytm przeszukiwania drzewa w głab.
¸
Dane wejściowe: drzewo .

odwiedzamy korzeń i wkładamy go na STOS; zaznaczamy jako wierzchołek
odwiedzony,

dopóki STOS nie jest pusty, powtarzamy:

jeżeli jest wierzchołkiem na wierzchu STOSU, to sprawdzamy, czy istnieje

syn wierzchołka , który nie był jeszcze odwiedzony, najpierw sprawdzamy ,
a potem .

jeżeli takie sie znajdzie, to odwiedzamy , wkładamy go na wierzch STO-
¸
SU i zaznaczamy jako wierzchołek odwiedzony,

jeżeli takiego nie ma, to zdejmujemy ze STOSU i cofamy sie do wierz-
¸
chołka bedacego na stosie pod spodem.
¸ ¸
Przykład 1.7 Poniższa tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest za-
wartość stosu po każdej kolejnej iteracji petli algorytmu, gdy przeszukiwane jest drzewo
¸
z rysunku 1.1.
10 Rozdział 1. Struktury danych
Wierzchołek STOS

0 ,0
00 ,0,00
0 ,0
01 ,0,01
0 ,0

1 ,1
10 ,1,10
1 ,1
11 ,1,11
110 ,1,11,110
11 ,1,11
111 ,1,11,111
11 ,1,11
1 ,1

W metodzie przeszukiwania w głab po każdym kroku algorytmu wierzchołki znajdujace
¸ ¸
sie na stosie tworza ścieżke od wierzchołka wejściowego do wierzchołka aktualnie od-
¸ ¸ ¸
wiedzanego. Zauważmy, że nazwa każdego wierzchołka na stosie jest prefiksem (przed-
rostkiem) nazwy nastepnego wierzchołka. Dlatego wystarczy przechowywać ostatnie bity
¸
wierzchołków na stosie. Nie jest też konieczne zaznaczanie, które wierzchołki były już
odwiedzone, wystarczy zauważyć, że:

jeżeli przyszliśmy do wierzchołka od jego ojca, to żaden z synów nie był jeszcze
odwiedzany,


jeżeli przyszliśmy do wierzchołka od lewego syna (po zdjeciu ze stosu), to
¸
odwiedzony był tylko lewy syn,

jeżeli przyszliśmy do wierzchołka od prawego syna (po zdjeciu ze stosu), to
¸
odwiedzeni już byli obaj synowie.
Oto prostsza wersja algorytmu przeszukiwania w głab:
¸
Algorytm przeszukiwania drzewa w głab (druga wersja).
¸
Dane wejściowe: drzewo .

odwiedzamy korzeń i wkładamy go na STOS,

dopóki STOS nie jest pusty, powtarzamy:

Jeżeli jest aktualnie odwiedzanym wierzchołkiem i

Jeżeli ostatnia operacja na stosi było włożenie nowego elementu, to:
¸ ¸



Jeżeli , to przejdz
do i włóż 0 na stos,


Jeżeli ale , to przejdz
do i włóż 1 na stos,
1.4. Przeszukiwanie drzew binarnych 11


Jeżeli oraz , to zdejmij ostatni element ze stosu i przejdz
do
ojca wierzchołka .

Jeżeli ostatnia operacja na stosie było zdjecie 0 to:
¸ ¸ ¸


Jeżeli , to przejdz
do i włóż 1 na stos,


Jeżeli , to zdejmij ostatni element ze stosu i przejdz
do ojca wierz-
chołka .

Jeżeli ostatnia operacja na stosie było zdjecie 1 to: zdejmij ostatni element ze stosu
¸ ¸ ¸
i przejdz
do ojca wierzchołka .
Przykład 1.8 Poniższa tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest za-
wartość stosu po każdej kolejnej iteracji petli drugiego algorytmu, gdy przeszukiwane jest
¸
drzewo z rysunku 1.1.
Wierzchołek STOS

0 ,0
00 ,0,0
0 ,0
01 ,0,1
0 ,0

1 ,1
10 ,1,0
1 ,1
11 ,1,1
110 ,1,1,0
11 ,1,1
111 ,1,1,1
11 ,1,1
1 ,1

Zauważmy, że etykiety na stosie zÅ‚aczone razem tworza nazw¸ aktualnie odwiedzanego
¸ ¸ e
wierzchołka.
1.4.2 Przeszukiwanie drzewa wszerz
Nastepny algorytm przeszukiwania drzew używa kolejki jako pomocniczej struktury da-
¸
nych.
Algorytm przeszukiwania wszerz.
Dane wejściowe: drzewo .

odwiedzamy korzeń drzewa i wkładamy go do KOLEJKI.
12 Rozdział 1. Struktury danych

dopóki KOLEJKA nie jest pusta, powtarzamy:

bierzemy jeden wierzchołek z poczatku KOLEJKI,
¸

odwiedzamy wszystkiech synów wierzchołka i wkładamy je na koniec
kolejki.
Poniżej przedstawiono odwiedzane wierzchołki oraz zawartość kolejki po każdej kolejnej
iteracji petli algorytmu przeszukiwania wszerz drzewa przedstawionego na rysunku 1.1.
¸
wierzchołki KOLEJKA

0,1 0,1
00,01 1,00,01
10,11 00,01,10,11
- 01,10,11
- 10,11
- 11
110,111 110,111
- 111
- -
W metodzie przeszukiwania wszerz wierzchołki sa przeszukiwane w kolejności od wierz-
¸
chołków bedacych najbliżej wierzchołka poczatkowego do wierzchołków bedacych dalej.
¸ ¸ ¸ ¸ ¸
1.4.3 Rekurencyjne algorytmy przeszukiwania drzew
Istnieje prosty i ciekawy sposób uzyskiwania postaci postfixowej wyrażenia arytmetycz-
nego z drzewa tego wyrażenia. Aby uzyskać postać postfixow¸ wyrażenia, należy prze-
a
szukać drzewo tego wyrażenia w pewien określony sposób, zwany przeszukiwaniem po-
storder.
Przeszukiwanie postorder. Aby przeszukać (pod)drzewo majace swój korzeń w wierz-
¸
chołku :


przeszukujemy jego lewe poddrzewo (z korzeniem w ),

przeszukujemy jego prawe poddrzewo (z korzeniem w ),

odwiedzamy wierzchołek (korzeń drzewa).
Algorytm ten możemy krótko przedstawić w schemacie:
lewe poddrzewo  prawe poddrzewo  korzeń.
Przykład 1.9 Jeżeli przeszukamy drzewo z rysunku 1.4 i wypiszemy po kolei etykiety od-
wiedzanych wierzchołków, to otrzymamy ciag:
¸



który jest postacia postfixowa wyrażenia .
¸ ¸
1.5. Drzewa poszukiwań binarnych 13
Istnieja jeszcze dwie inne pokrewne metody przeszukiwania drzew binarnych: inorder
¸
i preorder:
Przeszukiwanie inorder. Aby przeszukać (pod)drzewo majace swój korzeń w wierzchoł-
¸
ku :


przeszukujemy jego lewe poddrzewo (z korzeniem w ),

odwiedzamy wierzchołek (korzeń drzewa),

przeszukujemy jego prawe poddrzewo (z korzeniem w ).
Przeszukiwanie preorder. Aby przeszukać (pod)drzewo majace swój korzeń w wierz-
¸
chołku :

odwiedzamy wierzchołek (korzeń drzewa),


przeszukujemy jego lewe poddrzewo (z korzeniem w ),

przeszukujemy jego prawe poddrzewo (z korzeniem w ).
Przykład 1.10 Jeżeli przeszukamy drzewo z rysunku 1.4 metoda inorder, to etykiety utworza
¸ ¸
ciag:
¸


czyli wyrażenie w postaci infixowej, ale bez nawiasów. Przeszukanie tego samego drzewa
metoda preorder da ciag etykiet:
¸ ¸


Jest to tak zwana postać prefixowa wyrażenia. Znak operacji wystepuje w niej przed ar-
¸
gumentami. Podobne jak w postaci postfixowej, postać prefixowa da sie jednoznacznie
¸
rozkładać i nie wymaga nawiasów.
1.5 Drzewa poszukiwań binarnych
Drzewa sa podstawow¸ struktura przy budowie dużych baz danych. Jeda z najprostszych
¸ a ¸ ¸
takich struktur sa drzewa poszukiwań binarnych. Aby utworzyć drzewo poszukiwań bi-
¸
narnych, zaczynamy od pustego drzewa, a nastepnie wstawiamy po kolei elementy, któ-
¸
re maja być przechowywane w drzewie. Wstawiane elementy powinny być z jakiegoś
¸
uporzadkowanego zbioru. Poniżej przedstawiamy algorytmu wstawiania elementów do
¸

drzewa. oznacza wartość przechowywana w wierzchołku . Pamietajmy, że
¸ ¸
oznacza poddrzewo o korzeniu w wierzchołku .
Algorytm wstawiania elementu do drzewa poszukiwań binarnych.
Aby wstawić element do drzewa :



jeżeli drzewo jest puste, to (wstaw do korzenia ),
14 Rozdział 1. Struktury danych


w przeciwnym razie porównaj z zawartościa korzenia :
¸



jeżeli , to wstaw do poddrzewa ,


jeżeli , to wstaw do poddrzewa .

Przykład 1.11 Przypuśćmy, że mamy ciag liczb naturalnych:
¸



Utworzymy dla tego ciagu drzewo poszukiwań binarnych.
¸
Rysunek 1.5: Drzewo poszukiwań po wstawieniu elementów: 128, 76, 106, 402






Po wstawieniu pierwszych czterech elementów ciagu otrzymamy drzewo, które jest
¸
przedstawione na rysunku 1.5, a po wstawieniu całego ciagu otrzymamy drzewo, które
¸
jest przedstawione na rysunku 1.6. Jeżeli teraz przeszukamy to drzewo metoda inorder, to
¸
otrzymamy ten sam ciag, ale uporzadkowany:
¸ ¸




Jeżeli mamy już drzewo poszukiwań binarnych , to dla każdego wierzchołka
zachodzi



dla każdego , ,


dla każdego , .
Czyli wszystkie wierzchołki w lewym poddrzewie zawierają wartości mniejsze
od wartości w , a wszystkie wierzchołki w prawym poddrzewie zawierają wartości
mniejsze od wartości w .
Aby stwierdzić, czy jakiś element znajduje sie na tym drzewie. Postepujemy podob-
¸ ¸
nie jak przy wstawianiu elementów. Zaczynamy od korzenia drzewa i szukamy
elementu za pomoca poniższego algorytmu.
¸
1.6. Zadania 15
Rysunek 1.6: Drzewo dla ciagu: 128,76,106,402,100,46,354,1018,112,28, 396,35
¸












Algorytm szukania elementu na drzewie .
Aby stwierdzić, czy element znajduje sie na drzewie :
¸

jeżeli jest puste, to koniec, elementu nie ma na drzewie,


jeżeli nie jest puste, to porównujemy z wartościa :
¸


jeżeli , to koniec, znalez
liśmy element na drzewie,




jeżeli , to szukamy w lewym poddrzewie ,


jeżeli , to szukamy w prawym poddrzewie .

W drzewie poszukiwań binarnych czas wyszukiwania lub wstawiania elementu jest

¸
, gdzie jest wysokościa drzewa. W obu algorytmach tylko raz przechodzimy od
korzenia w dół do liścia. Najlepiej by było, gdyby wysokość drzewa była rzedu logarytm
¸
od liczby wierzchołków, ale nie w każdym drzewie poszukiwań binarnych tak musi być.
1.6 Zadania
1. Ile wierzchołków może mieć drzewo binarne wysokości ?
2. Przeszukaj metoda  w głab ( wszerz ) drzewo z rysunku 1.7.
¸ ¸


3. Narysuj drzewo dla wyrażenie . Przedstaw to wyrażenie w postaci
postfixowej i prefixowej.
16 Rozdział 1. Struktury danych
4. Narysuj drzewo dla wyrażenie . Przedstaw to wyrażenie w postaci

infixowej i prefixowej. Oblicz wartość tego wyrażenia. Przedstaw to wyrażenie w
postaci infixowej i prefixowej.
5. Wypisz w postaci infixowej, prefixowej i postfixowej wyrażenie przedstawione na
rysunku 7.
Rysunek 1.7: Drzewo wyrażenia





6. Narysuj drzewo poszukiwań binarnych dla nastepujacego ciagu liczb: 30, 43, 13, 8,
¸ ¸ ¸
50, 40, 20, 19, 22.
7. Narysuj drzewo poszukiwań binarnych dla nastepujacego ciagu słów: słowik, wró-
¸ ¸ ¸
bel, kos, jaskółka, kogut, dziecioł, gil, kukułka, szczygieł, sowa, kruk, czubatka.
¸
[Fragment wiersza Ptasie radio Juliana Tuwima]
8. Udowodnij, że każde drzewo o werzchoÅ‚kach ma kraw¸
edzi.
9. Udowodnij, że każde pełne drzewo binarne o liściach ma wierzchołków
wewnetrznych.
¸
Wskazówka. Drzewo binarne nazywa sie pełne, jeżeli każdy jego wierzchołek ma
¸
albo dwóch synów, albo nie ma synów wcale (jest liściem).