Czym jest skip list i jak osiąga on wyszukiwanie O(log n)?

Question

Accepted Answer

**Skip list** to posortowana linked list rozszerzona o wiele **"express lane"** poziomów. Wyższe poziomy omijają wiele węzłów, więc wyszukiwanie schorza i przesuwa się w prawo, osiągając **O(log n)** oczekiwany czas — jak probabilistyczne, prostsze alternatyw dla drzewa zrównoważonego. ## Struktura ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Każdy węzeł jest awansowany do wyższych poziomów z prawdopodobieństwem `p` (często 0.5), więc średnio każdy poziom ma połowę mniej węzłów niż poniżej. ## Wyszukiwanie ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Złożoność | Operacja | Oczekiwane | Przestrzeń | |---|---|---| | wyszukiwanie | O(log n) | O(n) | | wstawienie / usunięcie | O(log n) | — | ## Dlaczego to ważne - **Zalety:** znacznie prostsze do implementacji niż red-black/AVL; brak rotacji; łatwe wersje współbieżne (używane w Redis sorted sets, Java `ConcurrentSkipListMap`). - **Wady:** gwarancje probabilistyczne (nie worst-case); dodatkowe wskaźniki na węzeł. ## Kompromisy vs drzewa zrównoważone Skip listy dostarczają operacje o kolejności O(log n) podobne do drzewa z znacznie mniejszą ilością kodu i łatą współbieżnością bez blokad, co jest powodem, dla którego systemy takie jak Redis je wybierają. Są doskonałym przykładem wykorzystania **randomization** do zastąpienia złożonej logiki balansowania deterministycznego.