Список с пропусками: дерево без дерева

Коротко

Список с пропусками (skip list) даёт поиск, вставку и удаление за O(log n) в ОЖИДАНИИ - но это вообще НЕ дерево, а многоэтажный связный список. Внизу - обычный отсортированный список всех элементов. Над ним - «экспресс-полоса»: список примерно из половины элементов (тех, кому случайно выпал хотя бы 1-й уровень; этажи считаем с нуля), над ней - четверть, и так далее. Поиск идёт СВЕРХУ: по верхнему разрежённому списку прыгаешь далеко, спускаешься, когда следующий элемент перелетает цель, - как электричка-экспресс, потом местная. Уровень каждого элемента выбирают СЛУЧАЙНО (подбрасывая монетку), поэтому структура балансируется сама, без вращений и перестроек. Это ещё один облик «случайность вместо балансировки» - и очень простой в реализации.

Если ты понимаешь устройство skip list (этажи списков, экспресс-полосы), как идёт поиск сверху вниз и почему случайные уровни дают ожидаемые O(log n), листай до «Теперь сам».

Как думаешь, можно ли ускорить поиск в связном списке

В отсортированном МАССИВЕ поиск быстрый - двоичный, можно прыгать в середину. В отсортированном СПИСКЕ прыгать нельзя: только шаг за шагом, O(n). А что мешает прыгать? Отсутствие «дальних» ссылок - у каждого узла ссылка только на СОСЕДА. Добавим часть узлам ДОПОЛНИТЕЛЬНЫЕ ссылки, перепрыгивающие через несколько элементов, - получится «экспресс-полоса», по которой можно двигаться крупными шагами, а спускаться на обычную полосу лишь у цели. Сколько таких полос и кому давать дальние ссылки? Если аккуратно каждому второму - выйдет как двоичный поиск, но поддерживать это при вставках дорого. А если решать СЛУЧАЙНО (монетка: попал элемент на верхний этаж или нет) - структура сама себя сбалансирует в среднем, и вставка станет простой. Это и есть список с пропусками.

На что это похоже

Метро с экспрессами и обычными поездами. Внизу - линия со ВСЕМИ станциями (обычный поезд, идёт подряд). Над ней - экспресс, останавливающийся лишь на каждой крупной станции (перепрыгивает мелкие). Едешь к нужной станции: садишься на экспресс, гонишь мимо мелких, а когда следующая экспресс-остановка уже ЗА твоей целью - пересаживаешься на обычный поезд и доезжаешь местными. Экспресс сокращает путь в разы. Список с пропусками - такая сеть линий: верхние этажи - экспрессы (мало станций, большие прыжки), нижний - все станции; поиск начинает сверху и спускается к цели.

Механизм: этажи и случайные уровни

Структура - несколько связанных отсортированных списков-этажей:

уровень 3:  1 --------------------------------> 30
уровень 2:  1 ----------> 9 -------------------> 30
уровень 1:  1 --> 4 ----> 9 ----> 17 ---------> 30
уровень 0:  1 -> 4 -> 6 -> 9 -> 12 -> 17 -> 25 -> 30    (все элементы)

Нижний уровень 0 содержит ВСЕ элементы по порядку. Каждый следующий этаж - разрежённая выборка предыдущего. Поиск ключа x:

поиск(x):
    начать на ВЕРХНЕМ уровне у первого узла
    пока не внизу:
        идти вправо, пока СЛЕДУЮЩИЙ узел на этом уровне <= x
        если следующий перелетает x - СПУСТИТЬСЯ на уровень ниже
    внизу проверить, тот ли это ключ

Вставка: найти место (как в поиске), вставить в нижний уровень, а затем ПОДБРАСЫВАТЬ МОНЕТКУ - пока выпадает «орёл», поднимать новый узел на этаж выше (добавляя ему дальнюю ссылку). Так уровень элемента - случайная величина: в среднем половина элементов есть на уровне 1, четверть - на уровне 2, и т.д. Это даёт O(log n) этажей и O(log n) шагов на поиск - в ОЖИДАНИИ, без всякой явной балансировки.

Skip list - этажи отсортированных списков: нижний (ур.0) со всеми элементами, верхние разрежены. Поиск прыгает по верхним «экспрессам» и спускается у цели. Уровни случайны - баланс сам собой.

Правило

Список с пропусками - многоэтажный связный список: нижний уровень содержит все элементы по порядку, каждый верхний - случайную разрежённую выборку (примерно половину предыдущего). Поиск идёт СВЕРХУ: вправо по этажу, пока следующий узел не перелетает цель, затем спуск на уровень ниже. Уровень каждого элемента выбирают СЛУЧАЙНО (монеткой), поэтому этажей O(log n) и все операции O(log n) в ОЖИДАНИИ - без вращений и перестроек. Это «дерево без дерева»: та же логарифмическая скорость, но на списках и через случайность, и очень просто в реализации.

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

Разберём, откуда логарифм. Уровень элемента определяется серией подбрасываний монетки: на уровень 1 попадает элемент с вероятностью 1/2, на уровень 2 - 1/4, на уровень k - 1/2^k. Значит на уровне k в среднем n/2^k элементов, и уровни кончаются, когда там остаётся ~1 элемент: n/2^k ≈ 1 → k ≈ log₂ n. Итого этажей O(log n). Теперь шаги поиска: на каждом этаже мы делаем в среднем НЕ БОЛЬШЕ пары шагов вправо, прежде чем спуститься (потому что верхний этаж вдвое реже нижнего - между двумя соседями сверху снизу примерно два узла). Значит на спуск через O(log n) этажей приходится O(log n) шагов - всего O(log n) на поиск. Всё это в ОЖИДАНИИ, по монетке: как и у декартова дерева, случайность внутри даёт хорошую высоту независимо от данных, а плохой случай крайне маловероятен и не вызывается подобранным входом.

Разбор: почему skip list проще сбалансированного дерева

При равной асимптотике skip list часто выбирают за ПРОСТОТУ и удобство. Вставка не требует разбора случаев, вращений или перекраски: нашёл место, вставил в нижний список, подкинул монетку - сколько раз выпал орёл, на столько этажей поднял, добавив дальние ссылки. Удаление - убрать узел со всех его этажей. Никаких инвариантов формы поддерживать не нужно - баланс обеспечивает случайность. Это резко короче кода красно-чёрного дерева (особенно его удаления). Ещё skip list естественно дружелюбен к ПАРАЛЛЕЛЬНОМУ доступу: операции локальны (правят несколько ссылок), и существуют эффективные конкурентные реализации без глобальных блокировок - поэтому его используют, например, в конкурентных структурах (ConcurrentSkipListMap в Java). Цена та же, что у всех рандомизированных структур: O(log n) в ОЖИДАНИИ, а не гарантированно, плюс расход памяти на дальние ссылки (в среднем ~2 ссылки на элемент). Для большинства задач это отличный обмен: чуть больше памяти и вероятностная гарантия - за простоту и параллелизм.

Что ломается без этого

Первая ошибка - выбирать уровни НЕ случайно (например, детерминированно каждому второму): такую структуру дорого поддерживать при вставках (сдвигается вся раскладка этажей), теряется главное преимущество - простота; случайность и делает вставку локальной. Вторая - строить поиск снизу вверх или без спуска: поиск ОБЯЗАН идти сверху (с разрежённых этажей) и спускаться у цели, иначе никакого ускорения нет - будет обычный проход по нижнему списку O(n). Третья - думать, что skip list даёт O(log n) гарантированно: это ОЖИДАНИЕ, как у treap; в патологическом (крайне маловероятном) случае монетки все элементы окажутся на одном уровне и поиск станет O(n). Четвёртая - забыть при вставке/удалении обновить ссылки на ВСЕХ этажах узла: узел живёт сразу на нескольких уровнях, и все его дальние ссылки надо связать корректно.

Зачем это в работе

Список с пропусками - практичная альтернатива сбалансированному дереву, когда важны простота реализации и/или параллельный доступ. ConcurrentSkipListMap/ConcurrentSkipListSet в Java - конкурентные упорядоченные коллекции именно на skip list; базы данных и хранилища (Redis для sorted sets, LevelDB/RocksDB в memtable) используют skip list как упорядоченную структуру в памяти - за скорость вставки и лёгкость конкурентного доступа. Понимать его важно как ещё один ответ на вопрос «как держать O(log n)»: не деревом и не вращениями, а этажами списков и монеткой. И как завершение линии «случайность вместо балансировки»: декартово дерево, splay (амортизация/адаптация) и skip list показывают, что логарифмическая скорость достижима многими непохожими способами, а выбор диктуют вторичные требования - гарантия против ожидания, простота, параллелизм, адаптивность к нагрузке. Это и есть инженерная зрелость: видеть, что за одинаковым O(log n) стоят разные компромиссы.

Теперь сам

В списке с пропусками (см. схему: этажи 0-3 над элементами 1, 4, 6, 9, 12, 17, 25, 30) ищут ключ 17, начиная с верхнего этажа. Опиши путь и объясни, почему в среднем этажей и шагов выходит O(log n), а не O(n).

Ответ. Начинаем на ВЕРХНЕМ этаже (уровень 3) у первого узла 1. Следующий на этом этаже - 30, а 30 > 17 - перелёт, значит спускаемся. Уровень 2: у 1 следующий - 9, и 9 ≤ 17, шагаем в 9; следующий за 9 на этом этаже - 30, снова перелёт, спускаемся. Уровень 1: у 9 следующий - 17, это и есть цель - нашли (при желании можно спуститься на уровень 0 и убедиться). Всего два шага вправо и два спуска, хотя элементов восемь. Почему O(log n), а не O(n): этажей O(log n), потому что каждый верхний вдвое реже нижнего (монетка ½), и они кончаются, когда наверху остаётся ~1 элемент (n/2^k ≈ 1 → k ≈ log₂ n). А на каждом этаже мы делаем лишь пару шагов вправо перед спуском (верхний вдвое разрежённее). Итого O(log n) этажей × константа шагов = O(log n). Обычный список дал бы O(n), потому что там один этаж и прыгать некуда, - «экспрессы» сверху и дают ускорение.

Главное

Список с пропусками - «дерево без дерева»: многоэтажный связный список, нижний уровень со всеми элементами по порядку, каждый верхний - случайная разрежённая выборка (~половина предыдущего). Поиск идёт СВЕРХУ (вправо по «экспрессу», спуск когда следующий перелетает цель) за O(log n) в ОЖИДАНИИ. Уровень элемента задаёт МОНЕТКА при вставке (на уровень k с вероятностью 1/2^k), поэтому этажей O(log n) и баланс держится сам, без вращений и перестроек. Плюсы - простота (нет разбора случаев, как у красно-чёрного) и удобство ПАРАЛЛЕЛЬНОГО доступа (ConcurrentSkipListMap, Redis sorted sets, memtable в LevelDB/RocksDB). Минусы - O(log n) в ОЖИДАНИИ, а не гарантированно, и память на дальние ссылки. Завершает линию «случайность/адаптация вместо явной балансировки»: одна скорость - разные компромиссы.