| Operacja | Średnio | Najgorszy przypadek |
|---|
* zamortyzowany: uśredniony w długim ciągu operacji
Wizualizator struktur danych
Struktura danych to sposób przechowywania danych tak, aby na najczęściej zadawane pytania dało się szybko odpowiedzieć. Wybierz jedną z jedenastu klasycznych struktur, od stosu po drzewo czerwono-czarne, wpisz wartość i naciśnij operację. Każdy krok rozgrywa się na ekranie: który węzeł jest porównywany, które dowiązanie się zmienia, dlaczego drzewo się obraca albo wartość wędruje w górę, wraz ze zdaniem, które nazywa, co się dzieje. Kafelki liczą pracę każdej operacji, a tabela podaje jej czas działania. Wybierz strukturę, wpisz wartość i naciśnij operację. Każda operacja odtwarza się krok po kroku: wyróżnione węzły pokazują, co jest porównywane, przesuwane lub zmieniane, a wiersz pod obrazem mówi, co się dzieje i dlaczego. Wstecz, Krok, Odtwórz i Koniec pozwalają przejść kroki jeszcze raz. Wypełnij losowo i Wyczyść zaczynają od nowa, a Cofnij wycofuje operację. Kafelki pokazują rozmiar, wysokość drzew, pracę ostatniej operacji (porównania, próby lub przejścia do rodzica) i jedną liczbę ważną dla danej struktury; tabela podaje czas działania każdej operacji.
Jak to działa
- Wybierz strukturę, na przykład binarne drzewo poszukiwań, tablicę mieszającą albo trie. Zaczyna z losową zawartością; Wypełnij losowo i Wyczyść zaczynają od nowa.
- Wpisz wartość i naciśnij operację: push, dodaj do kolejki, wstaw, usuń, szukaj, przejście, union albo find. Kroki odtwarzają się same; Wstecz, Krok, Odtwórz i Koniec pozwalają przejść je jeszcze raz.
- Czytaj w wierszu pod obrazem, co robi każdy krok, obserwuj w kafelkach rozmiar, wysokość i pracę ostatniej operacji, i porównuj czasy działania w tabeli.
Listy, stosy i kolejki
Najprostsze struktury trzymają elementy w rzędzie. Stos działa tylko na jednym końcu, więc ostatni włożony element wychodzi pierwszy, jak w stosie talerzy; kolejka dodaje z tyłu i zdejmuje z przodu, jak kolejka do okienka. Kolejka tutaj mieszka w buforze cyklicznym: przód i tył krążą po stałej tablicy i po jej końcu zaczynają od początku, a gdy bufor się zapełni, elementy są kopiowane do dwa razy większego. Lista jednokierunkowa łączy węzły wskaźnikami, więc wstawienie na początek nic nie kosztuje, ale aby znaleźć ogon albo indeks, trzeba iść po dowiązaniach jedno po drugim.
Drzewa, kopce, tablice mieszające i zbiory
Binarne drzewo poszukiwań trzyma mniejsze wartości po lewej, a większe po prawej, więc wyszukiwanie z każdym krokiem połowi liczbę kandydatów, o ile drzewo pozostaje rozłożyste. Dbają o to drzewa AVL i czerwono-czarne, za pomocą rotacji, które można obejrzeć i które nazywają się od swojego przypadku. Kopiec trzyma na górze tylko najmniejszą albo największą wartość, a więcej kolejka priorytetowa nie potrzebuje. Tablica mieszająca skacze wprost do kubełka obliczonego z klucza i musi radzić sobie z kolizjami; trie dzieli prefiksy słów; union-find w niemal stałym czasie mówi, czy dwa elementy należą do tego samego zbioru.
Często zadawane pytania
Jakiej struktury danych powinienem użyć?
To zależy od pytań, które zadajesz najczęściej. Stos lub kolejka, gdy elementy są obsługiwane w kolejności nadejścia albo odwrotnej; tablica mieszająca, aby wyszukać klucz; zrównoważone drzewo poszukiwań, takie jak AVL lub czerwono-czarne, gdy potrzebujesz też kluczy w porządku albo najbliższego klucza; kopiec, gdy zawsze potrzebujesz tylko najmniejszego albo największego elementu; trie dla słów i prefiksów; union-find, aby śledzić łączące się grupy.
Czym różni się drzewo AVL od drzewa czerwono-czarnego?
Oba utrzymują binarne drzewo poszukiwań płytkim, więc każde wyszukiwanie, wstawienie i usunięcie zajmuje czas proporcjonalny do log n. Drzewo AVL jest wyważone ściślej, wysokości obu stron każdego węzła różnią się najwyżej o jeden, więc wyszukiwanie jest nieco szybsze. Drzewo czerwono-czarne dopuszcza większy luz i przy zmianach wymaga mniej rotacji, dlatego wiele bibliotek standardowych używa go w swoich posortowanych mapach i zbiorach.
Dlaczego tablica mieszająca może być wolna w najgorszym przypadku?
Jeśli wiele kluczy trafi do tego samego kubełka, wyszukiwanie musi sprawdzać je po kolei, tak jak w liście. Dobra funkcja skrótu rozkłada klucze równomiernie, a tablica rośnie, zanim się zbytnio zapełni, więc wyszukiwanie zajmuje średnio stały czas. Spróbuj tablicy o rozmiarze 10 z liczbami kończącymi się tą samą cyfrą albo ze słowami, które są swoimi anagramami, i zobacz, jak piętrzą się kolizje.
Co oznaczają liczby obok węzłów AVL?
To współczynniki wyważenia: wysokość lewego poddrzewa węzła minus wysokość jego prawego poddrzewa. W drzewie AVL każdy współczynnik musi wynosić −1, 0 lub +1. Gdy wstawienie lub usunięcie zrobi z któregoś +2 albo −2, drzewo obraca się w tym węźle; przypadek (LL, RR, LR lub RL) mówi, w którą stronę przechyla się nadmiarowa wysokość, i rozstrzyga między jedną a dwiema rotacjami.
Czy coś jest wysyłane na serwer?
Nie. Każda operacja działa w twojej przeglądarce, a zawartość każdej struktury jest zapisywana w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora