Rekurencyjne struktury danych: Listy i drzewa

Wypada na początek powiedzieć co nieco o rekurencji, jej wadach i zaletach. Potem na tej wytworonej bazie opisać o co chodzi w listach i drzewach i jakie mają zastosowanie.

Pamiętaj! Żyby zrozumieć rekurencję, najpierw trzeba zrozumieć rekurencję

Charakterystyczną cechą funkcji (procedury) rekurencyjnej jest to, że wywołuje ona samą siebie. Drugą cechą rekursji jest jej dziedzina, którą mogą być tylko liczby naturalne.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni, inny przykład zastosowania rekursji to Ciąg Fibonacciego.

Pojawia się pytanie, czy warto stosować rekursję? Odpowiedź nie jest jednoznaczna. Funkcje rekurencyjne mają dużą złożoność obliczeniową, a ponad to wymagają zastosowania wewnętrznego stosu. Należy więc ich unikać. Niestety zlikwidowanie rekursji jest czasami bardzo trudne i wymaga sporych umiejętności. Są jednak przypadki, w których likwidacja rekursji jest możliwa i prosta, na przykład omawiana przez nas silnia daje się przedstawić w postaci iteracji.

Lista jest to dynamiczna struktura danych zawierająca skończony ciąg elementów. Początek listy nazywamy głową, a koniec ogonem. List pusta nie posiada żadnych elementów i zarówno głowa jak i ogon są nieokreślone.

• Lista jednokierunkowa jest to lista, w której przechodzenie przez listę możliwe jest tylko w jednym kierunku - w kierunku ogona. Każde element listy oprócz wartości zawiera także wskaźnik na kolejny element w liście. Wyjątkiem jest ogon gdzie kolejny element jest nieokreślony. Wadą listy jednokierunkowej jest skomplikowane usuwanie elementów. Ponieważ do usunięcia elementu potrzebujemy wskaźnika zarówno na element następny (co jest łatwo dostępne) jak i poprzedni (co w liście jednokierunkowej wymaga przejścia przez listę).
• Lista dwukierunkowa jest to lista, która posiada informacje o swoim poprzedniku oraz następcy, co umożliwia poruszanie się w obu kierunkach (w stronę głowy jak i ogona). Wadą tej listy jest większe zużycie pamięci i skomplikowanie kodu, aczkolwiek operacja usuwania jest znacznie szybsza od tej w liście jednokierunkowej.
• Lista cykliczna jest to lista, w której ogon wskazuje na głowę. W związku z tym nie ma ani początku ani końca listy.
• Lista z wartownikiem posiada wyróżniony element zwany wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.

Istnieją dwie podstawowe implementacje listy:

• Tablicowa:
  Jak wskazuje nazwa, lista zaimplementowana w ten sposób opiera się na tablicy obiektów (lub rekordów) danego typu.
  Dopisanie elementu do listy to wstawienie elementu do tablicy:
  • jeśli ma ono nastąpić na końcu listy, będzie to kolejny element w tablicy
  • jeśli nowy element ma znaleźć się między innymi elementami, należy przesunąć o jedno pole w prawo wszystkie elementy o indeksie wyższym niż pole, na które będzie wstawiany obiekt; następnie w powstałą lukę wpisuje się nowy element
  Usunięcie elementu znajdującego się pod danym indeksem tablicy to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie wyższym.
  
  Zalety tej implementacji: prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy.
  Wady: niska elastyczność, szczególnie dotycząca rozmiaru tablicy, złożoność operacji wstawiania i usuwania.
  
  Implementację tablicową stosuje się tam, gdzie elastyczność nie odgrywa istotnej roli, a wymagana jest szybka i prosta nawigacja.


• Wskaźnikowa:
  W tej implementacji każdy obiekt na liście musi (co nie było konieczne w wersji tablicowej) zawierać dodatkowy element: wskaźnik do innego obiektu tego typu. Wynika to z faktu, że to wskaźniki są podstawą nawigacji w tym typie listy, a dostęp do jej elementów jest możliwy wyłącznie przez wskaźnik.
  
  Dopisanie elementu (dla prostej listy jednostronnej):
  • jeśli ma ono nastąpić na końcu listy, to wskaźnik wiążący w obiekcie ostatnim ustawia się na nowy obiekt danego typu
  • jeśli ma ono nastąpić wewnątrz listy, to najpierw tworzy się nowy obiekt danego typu i jego wskaźnik wiążący ustawia się na następnik elementu, za którym ma być wstawiany. Później wskaźnik poprzednika przestawia się na ten nowy obiekt. W tym przypadku bardzo ważna jest kolejność, której zachwianie jest częstą przyczyną błędów. Np. można najpierw przestawić wskaźnik poprzednika na nowy obiekt, co spowoduje bezpowrotną utratę dostępu do dalszych elementów listy, na które już nie będzie pokazywał żaden wskaźnik. Ustawienie wskaźnika nowego elementu na następnik nie będzie możliwe, bo nie będzie znany jego adres
  Usunięcie elementu jest odwrotne do wstawiania: w pewnym miejscu zapisuje się wskaźnik do usuwanego elementu (aby nie "zgubić" jego adresu), następnie wskaźnik wiążący poprzednika przestawia się na następnik, i dopiero w tym momencie zwalnia się pamięć po obiekcie usuwanym (do tego potrzebny jest ten wskaźnik tymczasowy).

Korzystając z listy można wyróżnić dwie, główne struktury danych:

• Stos – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka stosu można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.
  
  W powyższym opisie pojawiły się pewne operacje, jakie można wykonywać na stosie. Oto ich formalny zapis:
  • push(obiekt) – czyli odłożenie obiektu na stos
  • pop() – ściągnięcie obiektu ze stosu i zwrócenie jego wartości


• Kolejka – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).
  Specjalną modyfikacją kolejki jest kolejka priorytetowa – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet, który modyfikuje kolejność późniejszego wykonania. Oznacza to, że pierwsze na wyjściu niekoniecznie pojawią się te dane, które w kolejce oczekują najdłużej, lecz te o największym priorytecie.

W informatyce drzewa są strukturami danych reprezentującymi drzewa matematyczne. W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), toteż głównie do tego celu są stosowane. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).

Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Jeśli drzewo nie jest puste, tzn. liczba wierzchołków jest większa od zera, jeden z nich jest wyróżniony i nazywany korzeniem drzewa.
Ciąg krawędzi łączących węzły nazywa się ścieżką. Istnieje dokładnie jedna ścieżka łącząca korzeń z wszystkimi pozostałymi wierzchołkami.
Liczba krawędzi w ścieżce od korzenia do węzła jest nazywana długością – liczba o jeden większa określa poziom węzła. Wysokością drzewa jest największy poziom istniejący w drzewie.
Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła. Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem.
Wierzchołek jest rodzicem dla każdego swojego dziecka. Każdy węzeł ma dokładnie jednego rodzica, wyjątkiem jest korzeń drzewa, który nie ma rodzica.

Specjalne znaczenie w informatyce mają drzewa binarne, w których liczba dzieci ograniczona jest do dwóch. Szczególnie popularne są BST i ich różne odmiany, np. drzewa AVL, drzewa czerwono-czarne.

Drzewa które posiadają więcej niż dwoje dzieci są nazywane drzewami wyższych rzędów, np. drzewo trie, B-drzewo.

Podstawowe operacje na drzewach to:

• wyliczenie wszystkich elementów drzewa,
• wyszukanie konkretnego elementu,
• dodanie nowego elementu w określonym miejscu drzewa,
• usunięcie elementu.

Pod pojęciem przechodzenia drzewa rozumie się odwiedzanie kolejnych wierzchołków, zgodnie z zależnościami rodzic-dziecko. Jeśli przy przechodzeniu drzewa na wierzchołkach są wykonywane pewne działania, to mówi się wówczas o przechodzeniu:

• preorder - gdy działanie jest wykonywane najpierw na rodzicu, następnie na dzieciach
• postorder - gdy działanie jest wykonywane najpierw na wszystkich dzieciach, na końcu na rodzicu
• W przypadku drzew binarnych istnieje jeszcze metoda inorder, gdzie najpierw wykonywane jest działanie na jednym z dzieci, następnie na rodzicu i na końcu na drugim dziecku.