Teoria informatykiobiekt

lista z przeskokami

skip list → lista z przeskokami

Probabilistyczna struktura listowa z wieloma warstwami wskaźników, umożliwiająca wyszukiwanie i wstawianie w oczekiwanym czasie logarytmicznym.

Typ: obiekt
Pojęcie nadrzędne: lista powiązana
Kategoria: Teoria informatyki · Struktury danych liniowe
Źródło: Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM 1990

Zobacz też

Drzewo, w którym każdy węzeł ma co najwyżej dwoje dzieci, oznaczane jako lewe i prawe.

Drzewo prefiksowe, w którym ścieżka od korzenia koduje kolejne symbole klucza, a wspólne prefiksy współdzielą gałęzie.

Zrównoważone drzewo wyszukiwań o wielu kluczach w węźle, zaprojektowane do efektywnego dostępu blokowego na pamięci zewnętrznej.

Drzewo binarne z porządkiem: klucze w lewym poddrzewie ≤ klucz węzła ≤ klucze w prawym poddrzewie, co umożliwia wyszukiwanie.

Samobalansujące się drzewo wyszukiwań, w którym wysokości poddrzew każdego węzła różnią się o co najwyżej 1.

Samobalansujące się drzewo wyszukiwań z kolorowaniem węzłów, w którym niezmienniki kolorów gwarantują logarytmiczną wysokość.

Wdrażamy chatboty, agentów głosowych i automatyzacje dla MŚP. Pierwsza konsultacja jest bezpłatna.