Co to jest lista pominięć?

Lista pominięć to probabilistyczna struktura danych. Lista pomijania służy do przechowywania posortowanej listy elementów lub danych z połączoną listą. Umożliwia efektywne przeglądanie procesu elementów lub danych. W jednym kroku pomija kilka elementów całej listy, dlatego nazywa się ją listą pominięć.

Lista pominięć jest rozszerzoną wersją listy połączonej. Pozwala użytkownikowi bardzo szybko wyszukać, usunąć i wstawić element. Składa się z listy bazowej zawierającej zbiór elementów, która utrzymuje hierarchię powiązań kolejnych elementów.

Pomiń strukturę listy

Zbudowana jest z dwóch warstw: warstwy najniższej i warstwy górnej.

Najniższa warstwa listy pominięć to zwykła posortowana lista połączona, a górne warstwy listy pominięć przypominają „linię ekspresową”, w której elementy są pomijane.

Tabela złożoności listy Pomiń

Praca z listą pominięć

Weźmy przykład, aby zrozumieć działanie listy pominięć. W tym przykładzie mamy 14 węzłów, które są podzielone na dwie warstwy, jak pokazano na schemacie.

Dolna warstwa to wspólna linia łącząca wszystkie węzły, a górna warstwa to linia ekspresowa łącząca tylko główne węzły, jak widać na schemacie.

Załóżmy, że w tym przykładzie chcesz znaleźć 47. Rozpoczniesz wyszukiwanie od pierwszego węzła linii ekspresowej i będziesz kontynuować bieg po linii ekspresowej, aż znajdziesz węzeł równy 47 lub większy niż 47.

Na przykładzie widać, że 47 nie istnieje w linii ekspresowej, więc szukasz węzła mniejszego niż 47, czyli 40. Teraz przechodzisz do normalnej linii za pomocą 40 i szukasz 47, jak pokazano na schemacie.

Uwaga: Gdy znajdziesz taki węzeł na „linii ekspresowej”, przejdź od tego węzła do „normalnego pasa” za pomocą wskaźnika, a gdy będziesz szukać węzła na normalnej linii.

Pomiń listę podstawowych operacji

Na liście pominięć znajdują się następujące typy operacji.

Operacja wstawiania:Służy do dodania nowego węzła do określonej lokalizacji w określonej sytuacji.Operacja usuwania:Służy do usunięcia węzła w określonej sytuacji.Operacja wyszukiwania:Operacja wyszukiwania służy do przeszukiwania określonego węzła na liście pominięć.

Algorytm operacji wstawiania

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Algorytm operacji usuwania

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Algorytm operacji wyszukiwania

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

Przykład 1: Utwórz listę pominięć, chcemy wstawić te następujące klucze do pustej listy pominięć.

1. 6 z poziomem 1.
2. 29 z poziomem 1.
3. 22 z poziomem 4.
4. 9 z poziomem 3.
5. 17 z poziomem 1.
6. 4 z poziomem 2.

Lata:

Krok 1: Wstaw 6 z poziomem 1

Krok 2: Wstaw 29 z poziomem 1

Krok 3: Wstaw 22 z poziomem 4

Krok 4: Wstaw 9 z poziomem 3

Krok 5: Wstaw 17 z poziomem 1

Krok 6: Wstaw 4 z poziomem 2

Przykład 2: Rozważmy ten przykład, w którym chcemy wyszukać klucz 17.

Lata:

Zalety listy pominięć

1. Jeśli chcesz wstawić nowy węzeł na listę pominięć, wstawi on węzeł bardzo szybko, ponieważ na liście pominięć nie ma rotacji.
2. Lista pominięć jest prosta w implementacji w porównaniu z tablicą mieszającą i drzewem wyszukiwania binarnego.
3. Znalezienie węzła na liście jest bardzo proste, ponieważ przechowuje on węzły w posortowanej formie.
4. Algorytm listy pominięć można bardzo łatwo modyfikować w bardziej szczegółowej strukturze, takiej jak indeksowane listy pominięć, drzewa lub kolejki priorytetowe.
5. Lista pominięć jest solidną i niezawodną listą.

Wady listy pominięć

1. Wymaga więcej pamięci niż zrównoważone drzewo.
2. Wyszukiwanie wsteczne jest niedozwolone.
3. Lista pomijania przeszukuje węzeł znacznie wolniej niż lista połączona.

Zastosowania listy Pomiń

1. Jest używany w aplikacjach rozproszonych i reprezentuje wskaźniki i system w aplikacjach rozproszonych.
2. Służy do implementacji dynamicznej, elastycznej kolejki współbieżnej z niską rywalizacją o blokady.
3. Jest również używany z klasą szablonów QMap.
4. Indeksowanie listy pominięć jest używane w przypadku problemów z medianą.
5. Lista pominięć jest używana do wysyłania kodowania delta w wyszukiwaniu Lucene.