Список с пропусками (skip list): поиск за O(log n) без балансировки

Коротко

Skip list — вероятностная структура, которая даёт ту же скорость, что сбалансированное дерево, но без поворотов и правил балансировки.

Проблема связного списка

Отсортированный связный список позволяет вставлять элементы за O(1), если известно место. Но найти это место — O(n): приходится идти по одному узлу.

[1] → [4] → [7] → [9] → [12] → [17] → [21]

Чтобы найти 17, нужно пройти шесть узлов. Бинарный поиск неприменим — нет доступа по индексу.

Идея: экспресс-полосы

Уильям Пью в 1989 году предложил надстроить над списком дополнительные «этажи», где хранится только часть элементов.

уровень 3:  [1] ──────────────────────→ [17]
уровень 2:  [1] ────────→ [9] ────────→ [17]
уровень 1:  [1] → [4] → [7] → [9] → [12] → [17] → [21]

Поиск начинается с верхнего уровня и идёт вправо, пока следующий элемент не станет больше искомого. Тогда спускаемся на уровень ниже.

Аналогия — метро с экспресс-линиями. Едете по экспрессу до ближайшей станции перед нужной, потом пересаживаетесь на обычную ветку.

Если на каждом уровне остаётся половина элементов, высота получается log₂n, и поиск занимает O(log n).

Зачем случайность

Поддерживать ровно половину элементов на каждом уровне при вставках и удалениях дорого — это и есть та самая балансировка, от которой мы уходим.

Решение красивое: уровень нового узла определяется подбрасыванием монетки. Добавили узел на уровень 1, бросили монетку — орёл, поднимаем на уровень 2, снова орёл — на уровень 3, и так далее.

level = 1
while random() < 0.5 and level < MAX_LEVEL:
    level += 1

В среднем половина узлов окажется на уровне 1, четверть на уровне 2, восьмая часть на уровне 3. Ровно то распределение, которое нужно, — и совершенно бесплатно.

Это ключевая идея: вместо поддержания структуры мы полагаемся на вероятность. Гарантии становятся вероятностными, но на практике этого достаточно.

Реализация на Python

import random


class Node:
    __slots__ = ('key', 'forward')

    def __init__(self, key, level: int):
        self.key = key
        self.forward = [None] * level     # ссылки на каждом уровне


class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = Node(None, self.MAX_LEVEL)
        self.level = 1

    def _random_level(self) -> int:
        level = 1
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    def search(self, key) -> bool:
        current = self.head

        # идём сверху вниз
        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]

        current = current.forward[0]
        return current is not None and current.key == key

    def insert(self, key) -> None:
        update = [None] * self.MAX_LEVEL
        current = self.head

        # запоминаем, откуда спускались на каждом уровне
        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        if current.forward[0] and current.forward[0].key == key:
            return                        # дубликаты не храним

        new_level = self._random_level()

        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level

        node = Node(key, new_level)
        for i in range(new_level):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

    def delete(self, key) -> None:
        update = [None] * self.MAX_LEVEL
        current = self.head

        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        target = current.forward[0]
        if target is None or target.key != key:
            return

        for i in range(self.level):
            if update[i].forward[i] is target:
                update[i].forward[i] = target.forward[i]

        # убираем опустевшие верхние уровни
        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1

    def __iter__(self):
        node = self.head.forward[0]
        while node:
            yield node.key
            node = node.forward[0]


sl = SkipList()
for x in [3, 6, 7, 9, 12, 19, 17]:
    sl.insert(x)

print(list(sl))         # [3, 6, 7, 9, 12, 17, 19]
print(sl.search(12))    # True
print(sl.search(15))    # False

sl.delete(12)
print(list(sl))         # [3, 6, 7, 9, 17, 19]

Массив update — ключевая деталь: он запоминает, из какого узла мы спускались на каждом уровне. Именно эти узлы нужно перенаправить при вставке или удалении.

Сравнение с деревьями

Главные практические плюсы skip list — простота кода (нет поворотов и случаев балансировки) и удобство для конкурентного доступа: изменяются только локальные ссылки, что позволяет строить неблокирующие версии.

Диапазонные запросы тоже удобнее: найти начало за O(log n) и дальше идти по нижнему уровню.

Где применяется

Redis использует skip list для сортированных множеств (ZSET). Выбор объяснён автором именно простотой и удобством диапазонных операций.

LevelDB и RocksDB держат в памяти таблицу memtable на skip list.

Apache Lucene применяет пропуски в списках вхождений для быстрого перехода.

Java — ConcurrentSkipListMap в стандартной библиотеке, потокобезопасная альтернатива TreeMap.

Про вероятностные гарантии

Формально худший случай O(n) — если монетка каждый раз падает неудачно и все узлы окажутся на первом уровне. Но вероятность этого астрономически мала.

Для n = 10⁶ вероятность, что поиск займёт больше 3·log₂n шагов, меньше одной миллиардной. На практике skip list ведёт себя стабильно, и «плохих» входных данных для него не существует — в отличие от несбалансированного дерева, которое отсортированный ввод вырождает в список.

Это важное отличие: у skip list нет плохих входных данных, есть только маловероятное невезение генератора случайных чисел.

Частые ошибки

Забытый массив update. Без него непонятно, какие ссылки перенаправлять при вставке.

Обновление ссылок только на нижнем уровне. Узел выпадет из верхних уровней, и структура сломается тихо: поиск начнёт иногда промахиваться.

Слишком маленький MAX_LEVEL. При миллионе элементов нужно минимум 20 уровней, иначе структура выродится в список.

Вероятность 0.5 везде подряд. Значение можно настраивать: P = 0.25 даёт меньше памяти при чуть более медленном поиске. Redis использует именно 0.25.

Фиксированный seed генератора. Делает структуру предсказуемой — в теории это открывает возможность подобрать плохие входные данные.

Что запомнить

• Skip list — отсортированный связный список с дополнительными уровнями-экспрессами.
• Уровень узла выбирается случайно, что заменяет балансировку.
• O(log n) в среднем на все операции, плохих входных данных не существует.
• Проще дерева в реализации и гораздо удобнее для конкурентного доступа.
• Используется в Redis, RocksDB и ConcurrentSkipListMap в Java.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→