PL 
EnglishDomyślny
Українська⏭️ Lista z przeskokami — probabilistyczne wyszukiwanie zrównoważone
Skip list nakłada „pasy ekspresowe” na posortowaną listę wiązaną: każdy węzeł awansuje z prawdopodobieństwem ½, co daje oczekiwane O(log n) wyszukiwania dzięki przeskokom na wyższych poziomach i schodzeniu w dół.
O liście z pominięciami (skip list)
Lista z pominięciami, wprowadzona przez Williama Pugha w 1990 roku, to probabilistyczna struktura danych utrzymująca posortowaną sekwencję elementów rozłożoną na wielu warstwach list wiązanych. Dolna warstwa to pełna posortowana lista; każda wyższa warstwa działa jak „pas ekspresowy”, zachowując jedynie losowy podzbiór warstwy poniżej, przy czym każdy element jest niezależnie awansowany z prawdopodobieństwem p (zwykle 0,5). Wyszukiwanie, wstawianie i usuwanie osiągają oczekiwany czas O(log n) — dorównując zbalansowanemu BST — bez deterministycznego narzutu rebalansowania drzew AVL czy czerwono-czarnych.
Ta symulacja pozwala wstawiać i usuwać klucze całkowite, obserwując, jak wieża każdego węzła rośnie do losowej wysokości. Podświetlona ścieżka przeszukiwania podczas wyszukiwania pokazuje, jak algorytm schodzi przez pasy ekspresowe, zanim zejdzie do kolejnej warstwy, ilustrując, dlaczego średnia liczba porównań wynosi w przybliżeniu log1/p n.
Najczęściej zadawane pytania
Jak lista z pominięciami osiąga wyszukiwanie O(log n) bez deterministycznego balansowania?
Wysokość każdego węzła jest losowana niezależnie z rozkładu geometrycznego o prawdopodobieństwie sukcesu p, więc oczekiwana liczba węzłów na poziomie k wynosi n·pk. Wyszukiwanie zaczyna się na najwyższym poziomie, posuwa się jak najdalej, a następnie schodzi niżej — oczekiwana łączna liczba porównań wynosi log1/p n + 1/p, czyli O(log n). Losowość efektywnie balansuje strukturę w oczekiwaniu, bez żadnych jawnych rotacji.
Jaka jest złożoność czasowa listy z pominięciami w najgorszym przypadku?
Najgorszy przypadek to O(n) — na przykład jeśli każdy węzeł zostanie awansowany na każdy poziom — ale zdarza się to z wykładniczo małym prawdopodobieństwem. W praktyce listy z pominięciami są używane tam, gdzie probabilistyczne gwarancje są akceptowalne (np. posortowane zbiory Redis wewnętrznie używają listy z pominięciami), ponieważ gwarancje najgorszego przypadku ze zbalansowanych drzew rzadko są potrzebne w tych kontekstach.
Ile pamięci zużywa lista z pominięciami w porównaniu ze zbalansowanym BST?
Przy prawdopodobieństwie awansu p = 0,5 oczekiwana łączna liczba wskaźników na wszystkich poziomach wynosi 2n (każdy węzeł wnosi jeden wskaźnik na poziom, oczekiwana wysokość 1/(1−p) = 2). Standardowy węzeł drzewa czerwono-czarnego również przechowuje dwa wskaźniki dzieci plus wskaźnik rodzica i bit koloru, więc zużycie pamięci jest porównywalne; listy z pominięciami często mają nieco wyższe czynniki stałe ze względu na alokacje wież o zmiennej długości.
Jak wstawianie do listy z pominięciami utrzymuje posortowaną kolejność?
Wstawianie najpierw wyszukuje pozycję, do której należy nowy klucz (zapisując najbardziej wysunięty w prawo odwiedzony węzeł na każdym poziomie w tablicy aktualizacji), następnie generuje losową wysokość h dla nowego węzła, a na końcu wstawia go na każdy poziom od 0 do h−1, aktualizując wskaźniki do przodu zapisane podczas wyszukiwania. Jest to analogiczne do wstawiania do listy wiązanej, powtórzonego dla każdego aktywnego poziomu.
Jaka wartość prawdopodobieństwa awansu p daje najlepszą wydajność?
p = 0,5 balansuje oczekiwany czas wyszukiwania i pamięć: obniżenie p redukuje pamięć, ale zwiększa oczekiwaną liczbę porównań na poziom; podwyższenie p zwiększa pamięć. Oryginalna analiza Pugha pokazała, że p = 0,25 daje niemal ten sam oczekiwany czas przy 25% mniejszej liczbie wskaźników, a Redis używa p = 0,25 w swojej implementacji listy z pominięciami. Optymalny wybór zależy od stosunku odczytów do zapisów i ograniczeń pamięciowych aplikacji.
Jak lista z pominięciami wypada w porównaniu z binarnym drzewem poszukiwań przy współbieżnym użyciu?
Listy z pominięciami są często preferowane w środowiskach współbieżnych, ponieważ warianty bez blokad (lock-free) i bez oczekiwania (wait-free) są znacznie prostsze do zaimplementowania niż współbieżne zbalansowane BST. Listy z pominięciami bez blokad (np. algorytm Harrisa-Frasera-Shavita) wymagają jedynie atomowej operacji porównaj-i-zamień na pojedynczych wskaźnikach, podczas gdy współbieżne drzewa AVL czy czerwono-czarne muszą blokować lub starannie wersjonować całe łańcuchy rotacji. ConcurrentSkipListMap w Javie wykorzystuje to podejście.
Czy istnieje deterministyczna wersja listy z pominięciami?
Tak. Deterministyczne listy z pominięciami (zwane też listami z pominięciami 1-2 lub listami z pominięciami typu B) wymuszają dokładne zasady strukturalne zamiast polegać na losowaniu, gwarantując czas O(log n) w najgorszym przypadku. Wymagają jednak bardziej złożonej logiki wstawiania i usuwania, bliższej B-drzewu niż elegancka prostota rzutu monetą, która czyni probabilistyczne listy z pominięciami popularnymi.
Jakie rzeczywiste systemy używają list z pominięciami?
Redis używa listy z pominięciami do obsługi swojego typu danych Sorted Set, umożliwiając zapytania o rangę i skany zakresowe wg wyniku w czasie O(log n). Apache Cassandra wcześniej używała list z pominięciami dla swojego magazynu Memtable w pamięci. LevelDB i RocksDB używają wariantu dla swojego buforu zapisu w pamięci. ConcurrentSkipListMap i ConcurrentSkipListSet ze standardowej biblioteki Javy również są oparte na liście z pominięciami.
Jak przebiega usuwanie z listy z pominięciami?
Usuwanie lokalizuje węzeł i, dla każdego poziomu, na którym się pojawia, aktualizuje wskaźnik do przodu poprzednika, by go pominąć. Po odłączeniu wieża usuniętego węzła może zostać zwolniona. Jeśli usunięcie zmniejsza efektywną wysokość listy (tzn. górne poziomy stają się puste), licznik maksymalnego poziomu jest zmniejszany. Oczekiwany czas to O(log n), tak jak dla wyszukiwania.
Czy lista z pominięciami może efektywnie obsługiwać zapytania zakresowe?
Tak — to jedna z praktycznych zalet list z pominięciami nad tablicami mieszającymi. Po wyszukiwaniu O(log n) w celu znalezienia początku zakresu, lista wiązana na najniższym poziomie zapewnia przejście O(k), by zebrać wszystkie k elementów zakresu. Redis wykorzystuje to dla poleceń ZRANGEBYSCORE i ZRANGEBYLEX, kluczowych dla zastosowań tablic wyników i szeregów czasowych.