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").