1. STRUKTURY DANYCH

Struktury liniowe

Tablica

Opis:

określamy zwarty obszar pamięci, gdzie każda komórka przechowuje informacje określonego typu i do każdej z nich jest bezpośredni dostęp poprzez jej indeks.

Budowa:

Komórka: pojedyncza wartość, pole dwuelementowe, struktura

Złożoność obliczeniowa

Pobranie:

Dostęp do określonego elementu: natychmiastowy, ze względu na indeksowanie każdej komórki tablicy _ O(1).

Wyszukanie:

Wyszukanie elementu o określonej wartości: w najgorszym wypadku będziemy musieli odczytać wszystkie n komórek _ O(n).

Wstawienie:

Wstawienie nowego elementu na określoną pozycję: wstawienie nowego elementu na koniec tablicy wymaga po prostu powiększenia rozmiaru tablicy o 1 i wpisania wartości do ostatniej komórki (zatem jest to stała liczba operacji, niezależna od liczby elementów, czyli O(1)), jednak wstawienie nowego elementu w środek tablicy wymaga powiększenia rozmiaru tablicy o 1 oraz przesunięcia wszystkich elementów leżących na prawo od wstawianego o 1 pozycję w prawo, czyli w najgorszym wypadku (wstawienie elementu na pierwszą pozycję): stała liczba operacji zwiększania rozmiaru tablicy + n przesunięć + 1 zapisanie= O(1) + O(n) + O(1) = O(n).

Usunięcie:

Usunięcie elementu: analogicznie do wstawiania, w najgorszym wypadku (usunięcie pierwszego elementu) trzeba przesunąć n−1 elementów o 1 pozycję w lewo (n − 1 operacji) i zmniejszyć rozmiar tablicy o 1 (stała liczba operacji) _ O(n).

Lista jednokierunkowa

Opis:

jest to struktura wykorzystująca wskaźniki, gdzie każda komórka składa się z dwóch pól

Budowa:

każda komórka składa się z dwóch pól: pola danych (mogącego być _ jak w przypadku tablicy _ rozbudowaną strukturą) oraz wskaźnika na następny element. Ponadto, lista musi mieć (co najmniej) jedną wyszczególnioną komórkę zawierającą wyłącznie wskaźnik na pierwszy element , tzw. głowę.

Cechy charakterystyczne:

W porównaniu do tablicy, lista posiada tę zaletę , że nie musi być zwartym obszarem pamięci.

Złożoność obliczeniowa

Pobranie:

Dostęp do elementu: jeżeli element jest umieszczony na końcu listy, to aby do niego dotrzeć, trzeba przejrzeć wszystkie pozostałe n−1 elementów - O(n).

Wyszukanie:

Wyszukanie elementu: jak wyżej _ O(n).

Wstawienie:

Wstawienie elementu: należy utworzyć nową komórkę O(1), wypełnić wartość pola danych O(1), pole wska¹nika wypełnić wartością głowy O(1), a wartość głowy wypełnić wartością wskazującą na nowy element O(1) _ całkowity czas omawianej operacji wynosi zatem O(1).

Usunięcie:

Usunięcie elementu: wartość wska¹nika elementu poprzedzającego należy wypełnić wartością wskazującą na element następny O(n) (trzeba ten wska-¹nik znale¹ć!) i usunąć z pamięci dany element O(1) _ O(n).

Lista dwukierunkowa

Budowa:

każdy element, oprócz wartości i wska¹nika na następny element zawiera też wska¹nik na element poprzedzający , a oprócz głowy zawiera też (choć nie jest to konieczne) tzw. ogon, czyli wska¹nik na ostatni element struktury.

Złożoność obliczeniowa

Wyszukanie:

skraca operacje wyszukiwania elementu w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (O(n/2) = O(n)).

Wstawienie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu

(O(n/2) = O(n)).

Usunięcie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu

(O(n/2) = O(n)).

Lista cykliczna

Budowa:

wskaźnik ostatniego elementu wskazuje na pierwszy element

Złożoność obliczeniowa

jak wyżej

Lista samoorganizująca się

Opis:

elementy w strukturze są uporządkowane niemalejąco lub nierosnąco (względem wartości pól danych).

Cechy charakterystyczne:

Korzyści pojawiają się w niektórych szczególnych sytuacjach (gdy np. interesuj ą nas głównie maksymalne / minimalne elementy).

Złożoność obliczeniowa

Wstawienie:

operacji dodawania elementu _ należy utworzyć nową komórkę O(1), wypełnić wartość pola danych O(1), pole wska¹nika wypełnić wartością wskazującą na element, który ma być następnikiem elementu wstawianego (trzeba znale¹ć wartość tego wska¹nika, wyszukując element pierwotnie go poprzedzający O(n)), pole wska¹nika elementu poprzedzającego wypełnić wartością wskazującą na nowy element O(1) _ O(n).

Kolejka

Opis:

strukturą typu FIFO (ang. First In First Out), w której odczyt

następuje tylko z pierwszej pozycji, a wstawienie nowego elementu może nastąpić tylko na koniec struktury (za ostatni element).

Złożoność obliczeniowa

Pobranie: Wyszukanie:

dostęp (pobranie) oraz wstawienie nowego elementu zajmuje O(1)

Wstawienie: Usunięcie:

wyszukanie i usunięcie konkretnego elementu _ O(n).

Stos

Opis:

jest strukturą typu LIFO (ang. Last In First Out), czyli taką, w której dostęp (bezpośredni) jest tylko do pierwszego elementu, a dodanie nowego następuje przed pierwszy (na pierwszą pozycję).

Złożoność obliczeniowa

Pobranie: Wstawienie:

tak jak w przypadku kolejki _ złożoność operacji dostępu (pobrania) oraz dodania elementu wynosi O(1),

Wyszukanie: Usunięcie:

dla wyszukania i usunięcia konkretnego elementu to O(n).

Struktury nieliniowe

Drzewo ukorzenione

Opis:

Drzewo ukorzenione jest strukturą hierarchiczną,

Drzewo binarne- każdy element (nie będący liściem) posiada

co najwyżej dwóch potomków. Rozpatrzmy drzewo binarne pełne (liście tylko w ostatnim poziomie, dokładnie 2 potomków)

Budowa:

każdy element posiada element(y) podrzędny(e) i/lub element nadrzędny. Element nadrzędny nazywa się rodzicem, a podrzędny potomkiem. Wymogiem drzewa jest to, że każdy element może posiadać co najwyżej jednego rodzica i (w ogólności) dowolną liczbę potomków (_ 0). W drzewie wyróżniony jest element zwany korzeniem, który nie posiada rodzica (istnieje dokładnie jeden taki element). Z kolei elementy nie posiadające potomków zwane są liściami.

Cechy charakterystyczne:

Wychodząc od spostrzeżenia, że w każdym kolejnym poziomie drzewa jest dwa razy więcej elementów niż w poprzednim, liczbę wszystkich elementów można wyznaczyć jako sumę nast. ciągu geometrycznego, a0=1, q=2: 2⁰ + 2¹ + 2² + . . . + 2^k−1 = 2^{k − 1}= =n. Korzystając teraz z definicji logarytmu otrzymamy:

k = log2(n + 1), a zatem k = O(log n).

Kopiec

Opis:

takie drzewo binarne (prawie) pełne , w którym wartość rodzica jest zawsze nie mniejsza (nie większa) od obu potomków (w przypadku elementu bn/2c i nieparzystej liczby elementów _ od jedynego potomka).

Cechy charakterystyczne:

w korzeniu mamy zawsze element maksymalny (minimalny).

Biorąc pod uwagę powyższe, utworzenie poprawnego kopca ze zbioru n losowych wartości sprowadza się do n-krotnego wykonania operacji wstawienia elementu _ O(n log n).

Złożoność obliczeniowa

Pobranie:

Dostęp do elementu: w kopcu mamy dostęp tylko do korzenia O(1).

Wstawienie:

Wstawienie elementu: nowy element wstawiamy na koniec struktury i zamieniamy go z rodzicem dopóki rodzic jest mniejszy od wstawionego elementu _ O(log n).

Usunięcie:

Usunięcie (pobranie) elementu: procedura pobrania (pierwszego) elementu wymaga, po odczytaniu go z korzenia, przywrócenia właściwości kopca. Polega to na tym, że ostatni element ze struktury wstawiamy do korzenia (w miejsce pobranego elementu) i sukcesywnie zamieniamy go z większym z potomków dopóki ten potomek jest większy od zamienianego elementu. Zatem w najgorszym wypadku wykonamy O(log n) takich zamian, co stanowi złożoność obliczeniową całej procedury.

Drzewo poszukiwań binarnych

Opis:

(ang. Binary Search Tree, czyli drzewo BST), w którym dla każdego węzła, x, musi być spełniony następujący warunek:

wartość każdego elementu leżącego w lewym poddrzewie węzła

x jest nie większa niż wartość węzła x, natomiast wartość każdego elementu leżącego w prawym poddrzewie węzła x jest nie mniejsza niż wartość tego węzła.

Budowa:

wróćmy uwagę, że drzewo BST nie musi być pełne . Zatem jego liczba poziomów, k, może być większa niż log n (maksymalnie może wynosić n). Można jednak wykazać, że średnia wartość k dla losowo zbudowanego drzewa wynosi O(log n).

Złożoność obliczeniowa

Wyszukanie:

Dosyć łatwo dojść do tego, że wyszukanie elementu można wykonać w czasie O(k) (zaczynamy w korzeniu i schodzimy pojedynczą ścieżką w dół).

Wstawienie: Usunięcie:

Operacje wstawiania i usuwania również zajmują O(k) operacji (zasada wstawiania podobna jak przy wyszukiwaniu, usuwania nieco bardziej skomplikowana

Drzewo czerwono-czarne

Opis:

Są to takie drzewa BST, w których każdy węzeł posiada dodatkowy parametr - kolor, mogący przyjmować dwie wartości : czerwony lub czarny.

Dodatkowo, muszą być spełnione następujące warunki:

• każdy liść (NIL) musi być czarny,

• oba węzły potomne węzła czerwonego muszą być czarne,

• wszystkie ścieżki z danego węzła do liści mają tyle samo czarnych węzłów.

Budowa:

Dzięki temu każda ścieżka w drzewie jest co najwyżej dwa razy dłuższa niż dowolna inna, co zapewnia, że drzewo jest w przybliżeniu zrównoważone, a jego wysokość wynosi O(log n).

Tablice haszujące

Opis:

Służą one do efektywnego realizowania operacji słownikowych (wstawianie, wyszukiwanie, usuwanie).

Budowa:

Oczywiście efektywność tablicy haszującej ściśle zależy od czasu wyliczania funkcji haszujacej. Najlepiej, aby było to O(1). Prostym przykładem takiej funkcji może być h(k) = k mod m.

Inną ważną cechą, jaką powinna posiadać dobra funkcja haszująca, jest równomierne haszowanie, tzn. losowo wybrana wartość ma być z jednakowym prawdopodobieństwem odwzorowywana na każdą z m pozycji.

Kolejka i Stos są strukturami o specyficznych zastosowaniach i tylko dzięki nałożonym ograniczeniom posiadają korzystniejsze czasy dostępu lub wstawiania elementu (w stosunku do Tablicy i Listy).

• Kopiec ma korzystne czasy wstawiania i usuwania elementów w stosunku do pozostałych struktur (wprawdzie czasy wstawiania dla Listy, Kolejki i Stosu są szybsze, jednak suma czasów wstawiania i usuwania jest mniejsza właśnie dla Kopca).

• Kopiec nie jest dobrą strukturą do wyszukiwania elementów.