18. Listy i drzewa oraz ich zastosowania. Stosy i kolejki.

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. Aby dodać element do listy posortowanej należy sprawdzić, w którym miejscu powinien się on znajdować. Sprawdzamy od pierwszego elementu, schodząc do ostatniego. Jeśli element, który chcemy dodać, jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go między nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a wskaźnik tego elementu na następnik.

Podstawowe typy list to:

• lista jednokierunkowa, w której każdy element wskazuje na element następny, a element ostatni wskazuje na element pusty Ponieważ jest to lista jednokierunkowa, przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do pustej listy należy zapamiętać jego wskaźnik, by później móc się do niego odnieść.

• lista cykliczna, w której element ostatni wskazuje na element pierwszy

• lista dwukierunkowa, w której każdy element wskazuje zarówno na element poprzedni jak i następny. Listy dwukierunkowe umożliwiają łatwiejszy dostęp do danych niż listy jednokierunkowe.

Drzewo - rozumiane jako struktura danych umożliwia uporządkowanie obiektów w sposób hierarchiczny, a więc z określeniem podrzędności i nadrzędności. W takim drzewie istnieje jeden najważniejszy obiekt i on zajmuje miejsce, z którego drzewo wyrasta, czyli korzeń. W informatyce przyjęło się przedstawianie tej struktury danych odwrotnie, niż w naturze, tak więc korzeń znajduje się na samej górze drzewa. Pozostałe obiekty zajmują pozycje jego potomstwa i są umieszczane poniżej korzenia. Porządkowanie obiektów w strukturach drzewiastych jest często stosowane w algorytmice.

Wyróżniamy typy drzew:

a) z korzeniem - wyróżniony jest dokładnie jeden wierzchołek;

b) uporządkowane - ma korzeń, a kolejność dzieci każdego węzła jest ściśle określona;

c) m-drzewo - jest uporządkowane i każdy węzęł ma określoną liczbę dzieci;

Najczęściej stosowanym przypadkiem m-drzewa jest drzewo binarne. Jego cechą jest to, że każdy wierzchołek ma nie więcej niż dwoje dzieci.

Wyróżniamy odmiany drzewa binarnego:

● drzewo regularne - liczba dzieci każdego wierzchołka wynosi dokładnie 0 albo 2.

● binarne drzewo przeszukiwań (Binary Search Tree) - w każdym z węzłów drzewa BST przechowywany jest unikatowy klucz. Wartość klucza jest zawsze większa niż wartości wszystkich kluczy z lewego poddrzewa, a mniejsza niż wartości wszystkich kluczy z prawego poddrzewa (relacja może być odwrócona - to kwestia umowy); przechodząc rekurencyjnie drzewo metodą inorder (lewe dziecko, rodzic, prawe dziecko) uzyskuje się ciąg wartości posortowanych rosnąco. Wadą tego drzewa jest to, że trzeba je często wyważać. Natomiast zaletą przy wyważonym BST jest szybkie wyszukiwanie.

● AVL - drzewo BST, w którym każdy wierzchołek ma przypisany stopień wyważenia (o wartościach ze zbioru {-1, 0, 1}) zmieniany przy każdej operacji na drzewie. Jeżeli po dodaniu nowego węzła współczynnik wyważenia ma nieprawidłową wartość, to następuje wyważenie drzewa przez rotację węzłów.

● Kopiec (heap) zupełny - drzewo regularne, w którym liście występują na ostatnim i ewentualnie na przedostatnim poziomie (tylko gdy ostatni poziom nie jest całkowicie wypełniony); przy czym na ostatnim poziomie liście są spójnie ułożone od lewej do prawej. Ten ADT można zaimplementować przez drzewo rekordów, ale również przez tablicę. Wówczas w tablicy lewe dziecko węzła o indeksie n ma indeks 2n, a prawe 2n+1. Automatycznie rodzic węzła o indeksie n ma indeks n mod 2 niezależnie od tego czy jest lewym czy prawym dzieckiem.

d) b-drzewo - każdy węzeł zawiera węzły wewnętrzne. Węzeł może mieć dowolną liczbę dzieci. Węzły dzieci wychodzą od węzłów wewnętrznych. Ten typ drzewa ma zastosowanie w bazach danych, gdyż nie wymaga częstego wyważania.

Zastosowania drzew:

● sztuczna inteligencja - drzewo gry mini-max w algorytmie mini-max,

● systemy podejmowania decyzji - drzewo decyzyjne,

● grafika komputerowa - drzewo zachodzących na siebie obiektów na scenie,

● symulacja fizyki - drzewo kolizji obiektów na scenie,

● programowanie dynamiczne - drzewo wywołań rekurencyjnych funkcji,

● bazy danych - b-drzewo z danymi łatwo przeszukiwać.

● słowniki - drzewo AVL.

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ęsto 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. Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie elementy od aktualnego (czyli ostatniego), co wymaga czasu O(n).

Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi, np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.

Istnieje również inny typ kolejki kolejka priorytetowa, w której każdy element ma określony stopień ważności (priorytet). Wówczas przy pobieraniu elementów decyduje najpierw jego priorytet, a dopiero następnie kolejność.

---