Algorytmy i struktury danych · Senior · Pytanie 13 z 75
Czym jest skip list (lista z przeskokami)?
- ✓Poprawna odpowiedź: Posortowaną listą z losowymi „pasami ekspresowymi”
- 2Listą, która pomija duplikaty przy każdym wstawianiu
- 3Tablicą, z której usunięto co drugi element
Wyjaśnienie
Każdy węzeł dostaje losową wysokość; wyższe poziomy przeskakują więcej węzłów. Wyszukiwanie, wstawianie i usuwanie to średnio O(log n), a strukturę łatwiej uczynić współbieżną niż zbalansowane drzewo. Posortowane zbiory w Redis używają skip list.