Struktury danych wyjaśnione

Każdy program gdzieś przechowuje dane, a sposób przechowywania decyduje o tym, co jest szybkie, a co wolne. Listę miliona nazwisk można przeszukiwać nazwisko po nazwisku albo uporządkować tak, by dwadzieścia porównań znalazło dowolne nazwisko. Struktury danych to właśnie takie uporządkowania: garść pomysłów, w większości starszych niż komputer osobisty, które siedzą w każdej bazie danych, systemie operacyjnym, przeglądarce i grze.

Binarne drzewo poszukiwań w kolorach czerwonym i czarnym, stos pudełek, rząd kubełków tablicy mieszającej z łańcuchem kolidujących kluczy i strzałki łączące węzły listy
Binarne drzewo poszukiwań w kolorach czerwonym i czarnym, stos pudełek, rząd kubełków tablicy mieszającej z łańcuchem kolidujących kluczy i strzałki łączące węzły listy

Do czego służy struktura danych

Strukturę danych wybiera się według pytań, na które ma odpowiadać. Rejestr połączeń w telefonie potrzebuje najpierw ostatniego połączenia, kolejka drukarki najpierw najstarszego zadania, słownik znaczenia jednego słowa spośród stu tysięcy, planer tras najbliższego nieodwiedzonego skrzyżowania. Każda struktura przyspiesza niektóre operacje kosztem innych, a notacja O opisuje ten kompromis: O(1) oznacza, że czas nie rośnie z liczbą elementów n, O(log n), że podwojenie n dodaje jeden krok, a O(n), że czas rośnie proporcjonalnie do n.

Stosy, kolejki i deque

Stos dodaje i usuwa na tym samym końcu: ostatni wchodzi, pierwszy wychodzi. Historie cofania, przycisk Wstecz i wywołania działającego programu to stosy. Kolejka dodaje z tyłu i usuwa z przodu: pierwszy wchodzi, pierwszy wychodzi, jak naciśnięcia klawiszy albo kolejka wydruku. Deque pozwala na jedno i drugie na obu końcach. Wszystkie trzy działają w stałym czasie na operację. Kolejkę często trzyma się w buforze cyklicznym, stałej tablicy, w której przód i tył zawijają się za ostatnim miejscem; gdy się zapełni, elementy są kopiowane do tablicy dwa razy większej. Kopiowanie kosztuje O(n), ale zdarza się tak rzadko, że każda operacja nadal kosztuje średnio O(1), co nazywa się ograniczeniem zamortyzowanym.

Listy jednokierunkowe

Lista jednokierunkowa przechowuje każdą wartość w węźle ze wskaźnikiem na następny węzeł. Wstawienie albo usunięcie przestawia tylko jeden lub dwa wskaźniki, niczego nie trzeba przesuwać, ale nie da się skoczyć do dziesiątego węzła: idzie się po dowiązaniach od głowy. Lista, która pamięta tylko głowę, dochodzi do ogona w O(n) krokach; prawdziwe listy zwykle pamiętają też wskaźnik na ogon, a listy dwukierunkowe wskaźnik wstecz, i tak buduje się historię przeglądarki czy pamięć podręczną LRU.

Binarne drzewa poszukiwań

Binarne drzewo poszukiwań trzyma w każdym węźle mniejsze wartości w lewym poddrzewie, a większe w prawym. Wyszukiwanie porównuje i idzie w lewo albo w prawo, a przejście in-order odczytuje wartości posortowane. Usunięcie liścia to po prostu jego zdjęcie, węzeł z jednym dzieckiem zastępuje to dziecko, a węzeł z dwojgiem dzieci jego następnik in-order, najmniejsza wartość w prawym poddrzewie. Wszystko to zajmuje czas proporcjonalny do wysokości drzewa: około log n, gdy drzewo jest rozłożyste, ale n, gdy wartości przychodzą posortowane i drzewo degeneruje się do listy.

Drzewa AVL i czerwono-czarne

Drzewa samorównoważące naprawiają swój kształt po każdej zmianie. Drzewo AVL, wymyślone przez Adelsona-Wielskiego i Landisa w 1962 roku, utrzymuje wysokości dwóch poddrzew każdego węzła w odległości najwyżej jeden; gdy współczynnik wyważenia węzła osiąga ±2, jedna rotacja (przypadki LL i RR) albo dwie (LR i RL) przywracają równowagę. Drzewo czerwono-czarne koloruje węzły tak, że korzeń jest czarny, żaden czerwony węzeł nie ma czerwonego dziecka, a każda ścieżka w dół przechodzi przez tyle samo czarnych węzłów, co utrzymuje najdłuższą ścieżkę najwyżej dwa razy dłuższą od najkrótszej. Naprawia się przez przekolorowanie i co najwyżej kilka rotacji, i to ono siedzi w TreeMap w Javie, std::map w C++ i w planiście Linuksa.

Kopce i kolejki priorytetowe

Kopiec binarny to pełne drzewo binarne zapisane w tablicy bez żadnych wskaźników: dzieci pozycji i leżą pod 2i + 1 i 2i + 2. W kopcu min każdy rodzic jest najwyżej tak duży jak jego dzieci, więc najmniejsza wartość zawsze jest w korzeniu. Nowa wartość trafia na koniec i wędruje w górę przez większych rodziców; wyjęcie korzenia przenosi ostatnią wartość na szczyt i przesiewa ją w dół. Obie operacje kosztują O(log n), a całą tablicę można zamienić w kopiec w O(n). Kopce napędzają kolejki priorytetowe w algorytmie najkrótszych ścieżek Dijkstry, symulacjach zdarzeń i planistach systemów operacyjnych, i dają sortowanie przez kopcowanie.

Tablice mieszające

Tablica mieszająca zamienia klucz na indeks tablicy za pomocą funkcji skrótu i idzie prosto tam. Różne klucze mogą trafić pod ten sam indeks: to kolizja. Łańcuchowanie trzyma w każdym kubełku małą listę; adresowanie otwarte, takie jak próbkowanie liniowe, próbuje kolejnych miejsc, aż znajdzie wolne, a przy usuwaniu klucza musi zostawić nagrobek, aby późniejsze wyszukiwania próbowały dalej. Przy dobrej funkcji skrótu i niskim współczynniku wypełnienia (kluczy na kubełek), utrzymywanym przez powiększanie tablicy, wstawianie, wyszukiwanie i usuwanie kosztują średnio O(1). Słaba funkcja, na przykład sumowanie kodów znaków słowa, wysyła anagramy do tego samego kubełka. Tablice mieszające stoją za dict w Pythonie, obiektami JavaScriptu i indeksami baz danych.

Trie i union-find

Trie, czyli drzewo prefiksowe, przechowuje napisy po jednym znaku na poziom, więc słowa o tym samym początku dzielą ścieżkę, a węzeł oznacza, gdzie słowo się kończy. Znalezienie słowa o długości L zajmuje L kroków niezależnie od liczby zapisanych słów, a wszystkie słowa o danym prefiksie leżą w jednym poddrzewie: tak działają autouzupełnianie i sprawdzanie pisowni. Union-find trzyma elementy w zbiorach rozłącznych, z których każdy jest drzewem, a jego korzeń nazywa zbiór. Find idzie po dowiązaniach do rodzica aż do korzenia; union podwiesza jeden korzeń pod drugi. Z łączeniem według rangi i kompresją ścieżek długi ciąg operacji kosztuje niemal stały czas na operację, odwrotną funkcję Ackermanna α(n), która dla każdego realistycznego n wynosi najwyżej 4. Opiera się na tym algorytm Kruskala dla minimalnego drzewa rozpinającego.

Często zadawane pytania

Czym różni się tablica od listy jednokierunkowej?

Tablica trzyma elementy obok siebie w pamięci, więc każda pozycja jest dostępna od razu, ale wstawienie w środek oznacza przesunięcie wszystkiego, co jest dalej. Lista może wstawiać wszędzie przez zmianę wskaźników, ale dojście do pozycji oznacza marsz od głowy. Tablice znacznie lepiej wykorzystują też pamięć podręczną procesora, dlatego w praktyce zwykle są szybsze.

Co oznacza czas zamortyzowany?

Średni koszt jednej operacji w długim ciągu, nawet jeśli pojedyncza operacja bywa droga. Bufor cykliczny, który podwaja się po zapełnieniu, od czasu do czasu kopiuje wszystkie n elementów, ale ponieważ kopie stają się tym rzadsze, im większy jest bufor, n dodań kosztuje łącznie O(n), czyli średnio O(1) na jedno.

Czy kopiec to to samo co binarne drzewo poszukiwań?

Nie. Binarne drzewo poszukiwań umieszcza każde lewe poddrzewo przed swoim węzłem, a każde prawe po nim, więc potrafi wypisać wszystkie wartości w porządku i szybko znaleźć dowolną. Kopiec obiecuje tylko, że każdy rodzic jest przed swoimi dziećmi, co wystarcza, by od razu znaleźć minimum lub maksimum, ale nie, by szukać dowolnej wartości.

Skąd union-find wie, czy dwa elementy są połączone?

Idzie od każdego elementu po dowiązaniach do rodzica aż do korzenia jego drzewa. Jeśli oba dojdą do tego samego korzenia, są w tym samym zbiorze. Kompresja ścieżek sprawia potem, że każdy węzeł na drodze wskazuje bezpośrednio korzeń, więc kolejne pytanie o nie zajmuje jeden krok.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz wizualizator struktur danych