Drzewo binarne jest drzewem, dla którego kaŜdy ojciec ma co najwyŜej dwóch bezpośrednich synów.
Drzewo binarne to jeszcze nie uporządkowane drzewo
Drzewo AVL, nazywane równieŜ drzewem dopuszczalnym, to zrównowaŜone binarne drzewo poszukiwań
(BST), w którym wysokość lewego i prawego poddrzewa kaŜdego węzła róŜni się co najwyŜej o jeden.
ZrównowaŜenie drzewa osiąga się przypisując kaŜdemu węzłowi współczynnik wywaŜenia, który jest równy
róŜnicy wysokości lewego i prawego poddrzewa. własności drzewa AVL gwarantują, Ŝe pesymistyczny czas
wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n)
Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań, pozwala na szybkie
wyszukiwanie porównywalnych danych, kaŜdym węzłem powiązany jest dodatkowy atrybut, kolor, który moŜe
być czerwony lub czarny. 1. kaŜdy węzeł jest czerwony lub czarny2. kaŜdy liść (NULL) jest czarny 3. kaŜdy
czerwony węzeł ma czarne dzieci4. kaŜda prosta ścieŜka z ustalonego węzła do liścia (w dół drzewa) ma tyle
samo czarnych węzłów.
Przeszukiwanie wzorca:
Naiwny (brute force) o 1dno miejsce
KMP - tablica przesunięć next wzorzec porównywany do siedie(porówn 1wszy znak )o ile warto przesunąć
Algorytm Boyera i Moore’a
A B G B D
4 3 2 1 0 pozostałe litery 5 I mamy np. 4H->d0 więc 5+4=9 (pozycja na której będzie)
Rabina i Karpa z fragmentu tekstu liczbę i porównywany jest H
w
i H
T
x= t[i]*b
M−1
+… /mod p
sort wewnętrzny, jeśli dane uporządkowane są w postaci tablicy (zatem
mieszczą sie w pamięci operacyjnej RAM) oraz w procesie sortowania nie korzysta sie z tablic pomocniczych.
Dobra metoda sortowania powinna charakteryzować sie stabilnością. Metoda sortowania jest stabilna,
jeśli zachowuje względna kolejność elementów ze zdublowanymi kluczami.
Sortowania wewnętrzne:
Przez proste Wstawianie układanie kart zaczyna się od 2giego elementu
Przez Wstawianie Połówkowe dzielimy tablice na pół Dopóki l <=p wykonuj:
Oblicz indeks elementu środkowego m ze wzoru m = b (l + p)/2 c;
Jeśli element jest mniejszy od elementu am:
Odetnij prawa cześć tablicy przypisując p = m − 1;
W przeciwnym wypadku:
Odetnij lewa cześć tablicy, przypisując l = m + 1;
Przez proste Wybieranie (przez selekcje) wybieramy z całego ciągu element szukany najmniejszy największy i
wstawiamy go w miejsce poŜądane zastępując przy tym literę zamienioną z tą wstawioną miejscem
Bąbelkowe Porównywane 2 ostatnie elementy i zamieniane miejscami i kolejno ten przedostatni z przed-
przedostatnim
Szybkie (quicksort ) Zalety: czas proporcjonalny O(n log n) jest dość prosty w implementacji, biorąc pod uwagę
szybkość działania Wady: jest niestabilny, pesymistyczna złoŜoność tego algorytmu wynosi O(n2)
Bierzemy Ostatni element i zamieniamy go z 1wszym elementem który jest od niego (większy lub mniejszy)
Później juŜ sortowanie przebiega od początku tablicy kolejno
Sortowanie stogowe najpierw tworzony jest stóg z tablicy, później przesiewanie stogu
Sortowanie przez scalanie podział tablicy na 2 części, i dalej dzieli się na pół ,aŜ kaŜdy element będzie z
osobna , później następuje scalanie elementów i przy tym scalaniu występuje sortowanie.
Sortowania zewnętrzne: w przypadku ogromnej ilości danych lub niewielkiej dostępnej pamięci, W algorytmach
tych zakłada sie dostępność niewielkiego, pomocniczego obszaru pamięci
sortowanie przez scalanie dzieli się np. na 4 części i scalane są do siebie aŜ będzie jedna tablica
ZrównowaŜone scalanie trzykierunkowe tak jak poprzednio tylko występują takŜe dyski puste
Wielofazowe scalanie niezrównowaŜone wykorzystywana jest tablica rozdzielająca(gdzie jest blok atrapa) W
algorytmie scalania wielofazowego korzysta sie z podziału danych na części składające sie z róŜnej liczby
bloków. Po scalaniu pewnej liczby bloków, jeden z dysków pozostanie pusty.
PóŜniej następuje sortowanie przez scalanie bloków
Dysk Bloki Dysk Bloki
0 1, 4, 7, 10, 13, 15, 17 0 7, 10, 13, 15, 17
1 1 [1,2,3] , [4,5,6]
2 2, 5, 8, 11 2 8, 11
3 3, 6, 9, 12, 14, 16 3 9, 12, 14, 16 itd.
Haszowanie metoda wyszukiwania polegająca na porównywaniu wyszukiwanego
klucza z elementami przeszukiwanego zbioru. W haszowaniu próbuje sie uzyskać
bezpośrednie odniesienie do elementów w tablicy za pomocą operacji arytmetycznych przekształcających klucz
w odpowiedni adres tablicy. Alfabety jest kodowany Np. A=00001 W celu nie pomylenia się w wyszukiwaniu
(suma modulo, mnoŜenie, dzielenie)
Metody obsługi konfliktów : łańcuchowa , Tablice , Próbkowanie liniowe, Podwójne haszowanie
Rekurencja (inaczej rekursja - ang. recursion ) oznacza odwoływanie sie (np. funkcji lub definicji) do samej
siebie, Ze względu na niebezpieczeństwo powtarzania wywołań procedury (funkcji) w nieskończoność naleŜy
przestrzegać pewnych warunków zapewniających poprawność algorytmów zawierających procedurę (funkcje)
rekurencyjna. Przykłady: Obliczanie silni , quicksort
trochę o Drzewach BST : Przechodzenie drzewa BST
INORDER korzeń poddrzewa zostaje wypisany między wartościami z jego lewego i prawego poddrzewa
PREORDER wypisuje klucz korzenia przed wypisaniem wartości znajdujących się w obu poddrzewach
POSTORDER wypisuje klucz korzenia po wypisaniu wartości znajdujących się w poddrzewach
Usuwanie i wstawianie zobacz w materiałach!!!
Stóg jest drzewem binarnym, który posiada dwie własności. Pierwsza jest taka, Ŝe kaŜdy wierzchołek na stogu
jest niewiększy od swoich synów (o ile ich posiada). Druga własność polega na "pełności" tego drzewa. Jest to
uporządkowane drzewo binarne
Kopiec inaczej zwany stogiem jest szczególnym przypadkiem drzewa binarnego, które spełnia tzw.warunek
kopca tzn. kaŜdy następnik jest niewiększy od swego poprzednika. Z warunku tego wynikają szczególne
własności kopca:
* w korzeniu kopca znajduje się największy element
* na ścieŜkach (połączeniach między węzłami), od korzenia do liścia, elementy są posorotwane nierosnąco
Algorytm to szczegółowy przepis opisujący czynności, działania które powinny być wykonane przez
urządzenie, aby dojść do zamierzonego celu. KaŜdy program i gra komputerowa działają według określonego
algorytmu.
Lista jest to liniowo uporządkowany zbiór elementów, z których dowolny element moŜna usunąć oraz dodać w
dowolnym miejscu. Pierwszy i ostatni element listy nazywamy końcami listy. Szczególnym przypadkiem listy
moŜe być stos (gdy pobrać, odczytać i wstawić element moŜna tylko na końcu listy) lub kolejka (pobrać i
odczytać element moŜna tylko na początku listy, a dodać na końcu).
Listy mogą być posortowane (najmniejszy element jest w korzeniu). RozwaŜmy przypadek jednokierunkowej
listy posortowanej.
Stos jest strukturą liniowo uporządkowanych danych, z których jedynie ostatni element, zwany wierzchołkiem,
jest w danym momencie dostępny. W wierzchołku odbywa się dołączanie nowych elementów, równieŜ jedynie
wierzchołek moŜna usunąć.
Stos jest bardzo często wykorzystywaną strukturą danych. Działanie na nim jest częśto porównywane do stosu
talerzy: nie moŜna usunąć talerza znajdującego się na dnie stosu nie usuwając wcześniej wszystkich innych. Nie
moŜna takŜe dodać nowego talerza gdzieś indziej, niŜ na samą górę
Kolejka jest strukturą liniowo uporządkowanych danych w której dołączać nowe dane moŜna jedynie na koniec
kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku stosu,
z tą róŜnicą, Ŝe usuwamy dane od początku a nie od końca.
Cechy charakterystyczne poprawnego algorytmu:
1. Poprawność - dla kaŜdego przypisanego zestawu danych, po wykonaniu skończonej liczby czynności,
algorytm prowadzi do poprawnych wyników. 2. Jednoznaczność - w kaŜdym przypadku zastosowania
algorytmu dla tych samych danych otrzymamy ten sam wynik. 3. Szczegółowość - wykonawca algorytmu musi
rozumieć opisane czynności i potrafić je wykonywać. 4. Uniwersalność - algorytm ma słuŜyć rozwiązywaniu
pewnej grupy zadań, a nie tylko jednego zadania. Przykładowo algorytm na rozwiązywanie równań w postaci ax
+ b=0 ma je rozwiązać dla dowolnych współczynników a i b, a nie tylko dla jednego konkretnego zadania, np.
2x + 6 = 0
Program -zespół kodowanych instrukcji, określający dokładnie przebieg operacji arytmetycznych i logicznych
do wykonania przez komputer.
Tablica typ dany który przechowuje pary (unikalny klucz, wartość) i umoŜliwia dostęp do wartości poprzez
podanie klucza.
Metoda "dziel i zwycięŜaj" moŜe jedynie zostać zastosowana do problemów o strukturze rekurencyjnej, czyli
takich, których podproblemy "wyglądają" tak samo i dadzą się rozwiązać tą samą metodą.
Jak sama nazwa wskazuje metoda polega na podzieleniu problemu na kilka mniejszych podproblemów
(najczęściej na dwa, pół na pół), osobnym rozwiązaniu tych podproblemów i połączeniu wyników w jedno
rozwiązanie całego problemu. Oczywiście podproblemy rozwiązujemy w taki sam sposób (wszystko
rekurencyjnie), chyba Ŝe są na tyle małe (niepodzielne na mniejsze), Ŝe trzeba je "ręcznie" rozwiązać.
Np. sort przez scalanie
ZłoŜoność czasowa-czas działania algorytmu, wyraŜony liczbą jego operacji
ZłoŜoność czasowa pesymistyczna- ilość wykonywanych operacji elementarnych dla danych „najgorszego”
przypadku.
Pesymistyczna złoŜoność czasowa algorytmu to funkcja(max-to kres górny zbioru)
Lista jednokierunkowa jest oszczędna pamięciowa struktura danych pozwalająca grupować dodolna –
ograniczona iloscia dostepnej pamieci. Do budowy list jednokierunkowej uzywane sa dwa typy komorek
Pamieci.
Stabilnymi algorytmami nazywamy algorytmy w których jeśli 2 elementy w porządkowanym ciągu mają taka
samą wartość pewnej cechy , wg której odbywa się porządkowanie to ich kolejność względem siebie w
uporządkowanym ciągu jest taka sama jak w danym ciągu danym do posortowania
Procedura iteracyjna jest równowaŜna procedurze rekurencyjnej P, jeśli wykonuje dokładnie to samo zadanie
co P ,dając identyczne rezultaty. Wywoływanie rekurencyjne procedury P jest zwane terminalnym ,jeśli nie
następuje po nim juŜ Ŝadna instrukcja tej procedury. Procedury P1 i P2 są wzajemnie równowaŜne pod
warunkiem Ŝe P1 zawiera tylko jedno rekurencyjne wywołanie terminalne
Dwukopiec- swoja budowa przypomina kopiec, posiada dwóch potomków i dwóch przodków, na pierwszym
miejscu jest korzeń , interpretacja- tablica, kopiec jest drzewem binarnym Dwukopiec jest to graf z
wyróŜnionym wierzchołkiem r (korzeniem) taki, Ŝe (a) kaŜdy węzeł tego grafu, z wyjątkiem korzenia ma dwa
poprzedniki i kaŜdy węzeł, z wyjątkiem liści ma dwa następniki, (b) etykiety poprzedników są mniejsze od
etykiety węzła, a etykiety jego następników są większe, (c) ponadto, jeśli zbiór wierzchołków równoodległych
od korzenia nazwiemy poziomem w dwukopcu, to poziom ity ma i elementów o ile i(i+1)/2 < n, gdzie n jest
liczbą wierzchołków dwukopca, oraz jest wypełniony w sposób zwarty (bez "dziur").