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 Aukasiewicza. 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, znalezliś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).
Wyszukiwarka
Podobne podstrony:
Matematyka dyskretna 2002 09 Grafy nieskierowaneMatematyka dyskretna 2002 02 ArytmetykaMatematyka dyskretna 2002 11 Poprawność programówMatematyka dyskretna 2002 07 Rekurencjanotatek pl W,matematyka,Algorytmy i Struktury DanychAlgorytmy i struktury danych 08 Algorytmy geometryczneLista zadan nr 3 z matematyki dyskretnej2002 08 Programowana tablica świetlna19 struktury danych2002 08 Genialne schematyAlgorytmy Matematyka Dyskretna2002 08 Szkoła konstruktorówid!646Access 2002 Tworzenie bez danychwięcej podobnych podstron