Что такое skip list и как она достигает поиска O(log n)?

Question

Accepted Answer

**Skip list** — это упорядоченный связный список, дополненный несколькими уровнями **"express lane"**. Верхние уровни пропускают множество узлов, поэтому поиск спускается и движется вправо, достигая **O(log n)** ожидаемого времени — как вероятностная, более простая альтернатива сбалансированному дереву. ## Структура ```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) ``` Каждый узел повышается до более высоких уровней с вероятностью `p` (часто 0.5), поэтому в среднем каждый уровень содержит вдвое меньше узлов, чем уровень ниже. ## Поиск ```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 ``` ## Сложность | Операция | Ожидаемое | Память | |---|---|---| | поиск | O(log n) | O(n) | | вставка / удаление | O(log n) | — | ## Почему это важно - **Достоинства:** намного проще реализовать, чем red-black/AVL; без поворотов; легкие конкурентные версии (используются в Redis sorted sets, Java `ConcurrentSkipListMap`). - **Недостатки:** вероятностные гарантии (не наихудший случай); дополнительные указатели на узел. ## Компромиссы против сбалансированных деревьев Skip lists обеспечивают упорядоченные операции O(log n), подобные деревьям, с гораздо меньшим количеством кода и легкой безблокировочной параллелизмом, поэтому системы вроде Redis их выбирают. Они отличный пример использования **randomization** для замены сложной детерминированной логики балансировки.

Операция	Ожидаемое	Память
поиск	O(log n)	O(n)
вставка / удаление	O(log n)	—