Skip List
Skip List — это вероятностная структура данных, которая обеспечивает операции поиска, вставки и удаления за O(log n) в среднем случае, но при этом значительно проще в реализации, чем сбалансированные деревья поиска (AVL, Red-Black). Представьте многоуровневый железнодорожный вокзал: на нижнем уровне — все станции подряд (обычный связный список), на втором уровне — только половина станций (экспрессы), на третьем — только четверть, и так далее. Чтобы доехать из точки A в точку B, вы сначала едете на самом быстром экспрессе, пока не проскочите нужную станцию, затем спускаетесь уровнем ниже и продолжаете более медленным поездом. Это и есть Skip List в аналогии.
Ключевая идея: каждый узел с вероятностью p (обычно 0.5) поднимается на следующий уровень. При вставке мы «подбрасываем монетку» для каждого уровня: орёл — создаём ссылку на этом уровне, решка — останавливаемся. Это даёт случайную балансировку без необходимости сложных ротаций. Математически доказывается, что при p = 0.5 средняя высота структуры составляет O(log n), а каждая операция выполняется за O(log n) в среднем.
Когда применять / Мотивация
Заголовок раздела «Когда применять / Мотивация»Ключевая идея: каждый узел с вероятностью p (обычно 0.5) поднимается на следующий уровень. При вставке мы «подбрасываем монетку» для каждого уровня: орёл — создаём ссылку на этом уровне, решка — останавливаемся. Это даёт случайную балансировку без необходимости сложных ротаций. Математически доказывается, что при p = 0.5 средняя высота структуры составляет O(log n), а каждая операция выполняется за O(log n) в среднем.
Идея / Как работает
Заголовок раздела «Идея / Как работает»Когда применять: Skip List идеален для concurrent (многопоточных) сценариев. Redis использует Skip List для реализации sorted sets (ZSET), потому что структура позволяет эффективные lock-free операции — каждая вставка/удаление затрагивает только локальные указатели, в отличие от деревьев, где ротация может затронуть большую часть структуры. LevelDB и RocksDB используют Skip List для memtable. В Java есть ConcurrentSkipListMap, который обеспечивает thread-safe ordered map без глобальных блокировок.
Сложности:
Edge cases и частые ошибки: (1) Забыть обновить указатели на всех уровнях при вставке/удалении — это приведёт к разрыву структуры. (2) Не учесть, что новый узел может иметь высоту больше текущего максимума — нужно обновить head. (3) В concurrent версиях — забыть про memory ordering и ABA problem. (4) Худший случай O(n) возможен при неудачной последовательности случайных чисел (все узлы на уровне 0), но вероятность этого экспоненциально мала. (5) Range queries очень эффективны — просто идём по нижнему уровню от start до end, в отличие от деревьев, где приходится делать сложный in-order обход.
| Операция | Средний случай | Худший случай | Память |
|---|---|---|---|
| Search | O(log n) | O(n) | O(n) в среднем<br/>O(n log n) худший |
| Insert | O(log n) | O(n) | |
| Delete | O(log n) | O(n) |
Реализация
Заголовок раздела «Реализация»Задача: Реализовать SkipList с операциями search(target) → boolean, insert(num) → void, erase(num) → boolean. Дизайн должен поддерживать дубликаты. MaxLevel = 16, вероятность подъёма p = 0.5.
Подход: Создаём head-узел, который существует на всех уровнях (sentinel). Для поиска начинаем с максимального уровня, идём вправо, пока следующий узел меньше target, затем спускаемся на уровень ниже. Для вставки сначала выполняем поиск, запоминая последний узел на каждом уровне перед местом вставки (массив update). Генерируем случайную высоту нового узла. Если она превышает текущий maxLevel списка, обновляем maxLevel и update для новых уровней. Затем вставляем узел, обновляя указатели на всех уровнях от 0 до высоты узла. Для удаления аналогично ищем узел, запоминая update, затем удаляем, обновляя указатели на всех уровнях, где узел присутствовал.
class SkipListNode { constructor(val, maxLevel) { this.val = val; this.next = Array(maxLevel).fill(null); } }
class Skiplist { constructor() { this.maxLevel = 16; this.p = 0.5; this.level = 0; // текущий максимальный уровень в структуре this.head = new SkipListNode(-Infinity, this.maxLevel); }
randomLevel() { let lvl = 0; while (Math.random() < this.p && lvl < this.maxLevel - 1) { lvl++; } return lvl; }
search(target) { let curr = this.head; for (let i = this.level; i >= 0; i--) { while (curr.next[i] && curr.next[i].val < target) { curr = curr.next[i]; } } curr = curr.next[0]; return curr !== null && curr.val === target; }
add(num) { const update = Array(this.maxLevel).fill(null); let curr = this.head;
// Ищем позицию для вставки, запоминая последний узел на каждом уровне for (let i = this.level; i >= 0; i--) { while (curr.next[i] && curr.next[i].val < num) { curr = curr.next[i]; } update[i] = curr; }
const newLevel = this.randomLevel();
// Если новый узел выше текущего максимума if (newLevel > this.level) { for (let i = this.level + 1; i <= newLevel; i++) { update[i] = this.head; } this.level = newLevel; }
const newNode = new SkipListNode(num, this.maxLevel); for (let i = 0; i <= newLevel; i++) { newNode.next[i] = update[i].next[i]; update[i].next[i] = newNode; } }
erase(num) { const update = Array(this.maxLevel).fill(null); let curr = this.head;
for (let i = this.level; i >= 0; i--) { while (curr.next[i] && curr.next[i].val < num) { curr = curr.next[i]; } update[i] = curr; }
curr = curr.next[0]; if (!curr || curr.val !== num) return false;
// Удаляем узел на всех уровнях for (let i = 0; i <= this.level; i++) { if (update[i].next[i] !== curr) break; update[i].next[i] = curr.next[i]; }
// Понижаем уровень структуры, если верхние уровни пусты while (this.level > 0 && !this.head.next[this.level]) { this.level--; }
return true; } }
// Использование const skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); console.log(skiplist.search(0)); // false skiplist.add(4); console.log(skiplist.search(1)); // true console.log(skiplist.erase(0)); // false console.log(skiplist.erase(1)); // true console.log(skiplist.search(1)); // falseТрассировка
Заголовок раздела «Трассировка»Трассировка вставки add(3) в список [1, 2, 4]:
Текущее состояние (ASCII-диаграмма уровней): Level 2: HEAD → 2 → 4 → null Level 1: HEAD → 1 → 2 → 4 → null Level 0: HEAD → 1 → 2 → 4 → null
Шаг 1: Поиск позиции (начиная с level=2): i=2: curr=HEAD, next[2]=2 (val=2 < 3), двигаемся → curr=2 curr=2, next[2]=4 (val=4 ≥ 3), останавливаемся, update[2]=2 i=1: curr=2, next[1]=4 (val=4 ≥ 3), update[1]=2 i=0: curr=2, next[0]=4 (val=4 ≥ 3), update[0]=2
update = [2, 2, 2, null, null, ...]
Шаг 2: Генерация уровня для нового узла: randomLevel() → допустим, получили level=1 (два броска монетки: орёл, решка)
Шаг 3: newLevel=1 <= this.level=2, не расширяем верхние уровни
Шаг 4: Создаём newNode(val=3) и вставляем на уровнях 0 и 1: i=0: newNode.next[0] = update[0].next[0] = 4 update[0].next[0] = newNode Результат: 2 → 3 → 4 на уровне 0
i=1: newNode.next[1] = update[1].next[1] = 4 update[1].next[1] = newNode Результат: 2 → 3 → 4 на уровне 1
Итоговое состояние: Level 2: HEAD → 2 → 4 → null Level 1: HEAD → 1 → 2 → 3 → 4 → null Level 0: HEAD → 1 → 2 → 3 → 4 → nullСложность
Заголовок раздела «Сложность»Анализ сложности: Time: search, add, erase выполняются за O(log n) в среднем случае. Доказательство: каждый уровень пропускает примерно половину узлов нижнего уровня (из-за p=0.5), поэтому высота h ≈ log₂(n). На каждом уровне мы делаем O(1) сравнений в среднем (движемся вправо до первого узла ≥ target). Суммарно O(h) = O(log n). Худший случай O(n) — все узлы на уровне 0, но вероятность P(height > c log n) < 1/n^c → практически невозможно. Space: Каждый узел имеет в среднем 2 указателя (сумма геометрической прогрессии 1 + p + p² + … = 1/(1-p) = 2 при p=0.5). Итого O(2n) = O(n) в среднем, но O(n log n) в худшем случае (если все узлы имеют максимальную высоту).
Сравнение с AVL/Red-Black Tree: Асимптотика одинаковая, но константы лучше для Skip List в многопоточных сценариях. Реализация в 2-3 раза короче. Range queries проще и быстрее (просто проход по связному списку на уровне 0). Недостаток: требует больше памяти (в среднем 2n указателей против log n в деревьях). Детерминированные деревья дают гарантированный O(log n) даже в худшем случае, Skip List — только в среднем.
Типичные ошибки и подводные камни
Заголовок раздела «Типичные ошибки и подводные камни»(1) Интервьюер может спросить: “Зачем Redis выбрал Skip List вместо Red-Black Tree для ZSET?” — Ответ: проще реализация, эффективнее range queries (ZRANGE просто бежит по уровню 0), лучше для lock-free concurrent версий. (2) “Как обеспечить детерминированную производительность?” — Можно ограничить максимальную высоту узла и использовать детерминированные уровни (Deterministic Skip List), но теряем простоту. (3) “Почему p=0.5, а не другое значение?” — При p=0.5 оптимальное соотношение высоты и количества указателей. При p=0.25 структура выше, но меньше указателей на узел. (4) “Сравните с B-Tree” — B-Tree лучше для дисковых структур (locality, меньше seeks), Skip List — для in-memory concurrent. (5) Не забудьте обработать удаление последнего узла на верхних уровнях — нужно понижать this.level.
Follow-up вопросы интервьюера
Заголовок раздела «Follow-up вопросы интервьюера»- Как реализовать range query [min, max]? — Сначала поиском находим первый узел ≥ min (аналогично search, но на уровне 0 не останавливаемся), затем идём по уровню 0, пока node.val ≤ max, собирая значения. Сложность O(log n + k), где k — количество элементов в диапазоне.
- Можно ли сделать Skip List lock-free для многопоточности? — Да, используя CAS (compare-and-swap) для атомарного обновления указателей. Ключевая идея: вставка/удаление меняют только локальные указатели, не затрагивая глобальную структуру. ConcurrentSkipListMap в Java использует этот подход с дополнительными marker-узлами для обозначения удалённых элементов.
- Как изменить реализацию для хранения ключ-значение (map вместо set)? — Добавить поле key и value в узел, сравнивать по key. При insert проверять существование ключа и обновлять value вместо вставки дубликата.
- Что произойдёт, если randomLevel всегда возвращает 0? — Структура деградирует в обычный связный список, все операции станут O(n). Это демонстрирует важность случайности для балансировки.
- Как оценить вероятность худшего случая O(n)? — Вероятность, что узел имеет высоту ≥ k, равна p^k. Для всех n узлов вероятность, что хотя бы один имеет высоту > c log n, равна n · p^(c log n) = n · n^(-c log p) → 0 при росте n (для c > 1/log(1/p)). Поэтому высота практически всегда O(log n).
- Как реализовать операцию getRank(value) — позицию элемента в отсортированном порядке? — Добавить в каждый узел поле span на каждом уровне — количество узлов, которые “перепрыгивает” эта ссылка на уровне 0. При поиске суммируем span по пути. Redis ZSET использует этот подход для операций ZRANK/ZREVRANK. Добавление span усложняет insert/delete — нужно пересчитывать span для затронутых узлов.
Чеклист на собес
Заголовок раздела «Чеклист на собес»- Объяснил идею: уровни как «экспрессы», подъём узла на уровень — независимый бросок монетки с p=0.5.
- Знаю, что O(log n) — это среднее, а не гарантированное; худший случай теоретически O(n), но вероятность исчезающе мала.
- Привожу реальные применения: Redis ZSET, LevelDB/RocksDB memtable, Java ConcurrentSkipListMap.
- Реализация: head-sentinel на всех уровнях, массив update[] для запоминания «откуда падать» при поиске.
- При insert обновляю maxLevel, если новый узел выше; при erase — понижаю maxLevel, если верхние уровни опустели.
- Готов сравнить с AVL/RB-tree: те же O(log n), но Skip List проще, лучше для concurrent и для range queries.
- Если спросят про rank/order statistics — добавляется поле span на каждом уровне (как в Redis).