Struktury danych: pytania do ćwiczeń z wyjaśnieniami

1Czym jest struktura danych

Struktura danych to sposób organizowania danych w pamięci tak, aby pewne operacje były szybkie: znalezienie elementu, dodanie go, usunięcie.

Żadna struktura nie jest szybka we wszystkim. Wybór jednej oznacza wybór, które operacje mają być tanie. Ich koszty zapisuje się w notacji dużego O, gdzie n to liczba elementów.

Dwa podstawowe elementy składowe to tablica i lista wiązana.

Tablica przechowuje elementy w jednym bloku pamięci, jeden po drugim. Komputer może obliczyć, gdzie jest element i, więc odczyt a[i] zajmuje O(1). Wstawienie na początku oznacza przesunięcie każdego elementu: O(n).

Lista wiązana przechowuje każdy element w węźle ze wskaźnikiem na następny węzeł. Ostatni wskaźnik jest pusty (null). Wstawienie na początku (głowie, h) zmienia tylko jeden wskaźnik: O(1). Ale aby dotrzeć do elementu i, trzeba przejść i wskaźników: O(n).

Lista dwukierunkowa ma też wskaźnik na poprzedni węzeł, więc można przechodzić w obie strony.

2Stosy i kolejki

Stos jest jak stos talerzy: dodajesz i zdejmujesz tylko na górze. Ostatni element, który wszedł, wychodzi pierwszy: LIFO.

• push kładzie element na wierzchu, pop zdejmuje wierzchni element, peek odczytuje wierzch bez zdejmowania. Wszystkie są O(1).
• Zastosowania: funkcja cofania w edytorze, stos wywołań programu, sprawdzanie, czy nawiasy są zbilansowane, przeszukiwanie w głąb.

Kolejka jest jak kolejka do kasy: dołączasz na końcu i odchodzisz z początku. Pierwszy element, który wszedł, wychodzi pierwszy: FIFO.

• enqueue dodaje na końcu, dequeue usuwa z początku. Obie są O(1).
• Zastosowania: zadania drukowania, wiadomości czekające na obsłużenie, przeszukiwanie wszerz.

Deque (kolejka dwustronna) pozwala dodawać i usuwać na obu końcach. Kolejka priorytetowa zawsze najpierw usuwa element o najwyższym priorytecie; zwykle jest zbudowana jako kopiec.

3Drzewa, kopce, tablice mieszające i grafy

Drzewo ma jeden węzeł na szczycie, korzeń. Każdy inny węzeł ma dokładnie jednego rodzica. Węzły bez dzieci to liście. Drzewo z n węzłami ma n − 1 krawędzi.

W drzewie binarnym każdy węzeł ma co najwyżej dwoje dzieci. Binarne drzewo poszukiwań (BST) dodaje regułę: klucze w lewym poddrzewie są mniejsze od węzła, a klucze w prawym poddrzewie większe.

Przeszukiwanie BST idzie jedną ścieżką w dół, więc kosztuje O(wysokość). Drzewo zrównoważone (AVL, czerwono-czarne) utrzymuje wysokość blisko log₂ n. Klucze wstawiane w kolejności rosnącej tworzą łańcuch o wysokości n.

Kopiec to drzewo binarne, w którym każdy rodzic jest mniejszy od swoich dzieci (kopiec minimalny) albo większy (kopiec maksymalny). Minimum lub maksimum jest w korzeniu, a wstawianie i usuwanie kosztują O(log n).

Tablica mieszająca przechowuje pary klucz–wartość. Funkcja skrótu zamienia klucz na indeks, więc wstawianie i wyszukiwanie zajmują średnio O(1). Dwa klucze o tym samym indeksie to kolizja, rozwiązywana przez łańcuchowanie (lista na każde miejsce) lub adresowanie otwarte (próba innego miejsca).

Graf ma wierzchołki połączone krawędziami, które mogą mieć kierunek lub wagę. Przechowuje się go jako macierz sąsiedztwa, pamięć O(V²), albo jako listy sąsiedztwa, O(V + E).

4Metoda krok po kroku

Pytania często opisują zadanie i pytają, jaka struktura pasuje, albo pytają, jak wygląda struktura po kilku operacjach.

1. Znajdź operację, która musi być szybka: dostęp według pozycji, według klucza, najnowszy element, najstarszy element, najmniejszy element albo zakres.
2. Dopasuj do struktury: indeks → tablica, klucz → tablica mieszająca, najnowszy → stos, najstarszy → kolejka, najmniejszy lub największy → kopiec, kolejność posortowana lub zakresy → zrównoważone drzewo poszukiwań.
3. Sprawdź w notacji dużego O koszt pozostałych operacji, których potrzebuje zadanie.
4. W zadaniu typu „śledzenie” wykonuj operacje po kolei i zapisuj stan po każdej z nich.
5. Sprawdź stan końcowy z regułą struktury: LIFO, FIFO, porządkiem BST lub porządkiem kopca.

5Przykład krok po kroku

Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.

6Typowe błędy

• Mylenie LIFO z FIFO. Stos zwraca najnowszy element, kolejka najstarszy.
• Myślenie, że lista wiązana daje szybki dostęp według indeksu. Musi ona iść od głowy.
• Zakładanie, że BST zawsze jest O(log n). Tylko drzewo zrównoważone takie jest; wstawianie posortowane daje O(n).
• Zapominanie o kolizjach w tablicy mieszającej. O(1) to średnia, a nie przypadek pesymistyczny.
• Mylenie przemarszów. Preorder: węzeł najpierw. Inorder: węzeł w środku. Postorder: węzeł na końcu.
• Użycie macierzy sąsiedztwa dla dużego rzadkiego grafu. Marnuje ona pamięć O(V²).

7Jak wyglądają zadania egzaminacyjne

• Łatwe: pojęcia i fakty. LIFO i FIFO, czym jest węzeł, korzeń lub liść, reguła BST, co robi funkcja skrótu.
• Średnie: stosowanie pojęć. Która struktura pasuje do zadania, wynik operacji push i pop lub wstawień do BST, przemarsze drzew, tablica mieszająca z próbkowaniem liniowym, koszty w notacji dużego O.
• Trudne: przypadki i analiza. Drzewa zrównoważone, kopce w tablicach, B-drzewa, drzewa trie, union-find, filtry Blooma i projekty takie jak pamięć podręczna LRU.

Dla kopca przechowywanego w tablicy od indeksu 0 dzieci indeksu i znajdują się pod 2i + 1 i 2i + 2, a jego rodzic pod ⌊(i − 1) / 2⌋.