Список с пропусками
Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за времени выполнять операции добавления, удаления и поиска элементов.
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем , то он соответственно расположен и на всех уровнях , где .
Содержание
Построение
Допустим, что нам задан односвязный отсортированный список.
Тогда на первом уровне мы расположим заданный список, на втором только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем с номерами, кратными , и так далее. Такой список будет позволять в среднем за выполнять операции поиска, добавления и удаления элементов.
Функция возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
list buildLvl (list lvl) // Отсеивание нечётных элементов
list nextLvl
node i = lvl.head() // Перебор всех элементов lvl
while (i != null) and (i != lvl.tail())
nextLvl.push_back(node(i.key, i)) // Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня
i = i.next.next // Переход к следующему чётному элементу
return nextLvl
Функция принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
list skipList (list l):
list lvl = buildLvl(l) // Построение первого уровня
while lvl.size() > 2 // Добавление следующих уровней; последний содержит не более двух элементов
lvl = buildLvl (lvl)
return lvl // Возвращает ссылку на начало верхнего уровня
Операции над структурой
Поиск элемента
Допустим, что в нашем списке с пропусками существуют уровней, при этом первым уровнем будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
- Начинаем поиск элемента в верхнем списке (), рассмотрим первый элемент
- Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
- Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне выйти из поиска
Пример поиска числа в списке из описания:
Если в качестве случайного источника использовать честную монету, то тогда если в списке будет элементов, то количество уровней в среднем будет равно . Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего , откуда вытекает оценка времени поиска элемента в .
T find (list skip_list, K key)
node res
for (res = skip_list.head; res.ref != null; res = res.ref) // Пока ещё не дошли до первого уровня
while res.key < key // Переходим к следующему элементу
res = res.next()
return res.data
Вставка элемента
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
- Найти с помощью алгоритма поиска позицию, где мог бы находиться элемент.
- Вставить наш элемент в текущий уровень списка с пропусками
- Подбросить монету.
- Если выпал «Орёл» то перейти на уровень выше и вернуться к шагу
- Иначе закончить операцию вставки
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется , на третьем уровне и т.д. На уровне у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это , на третий и т.д. Вероятность попасть на уровень равна .
Используя монетку с распределением отличным от , можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением математическое ожидание количества элементов на уровне равно , на каждом следующем уровне будет в среднем в раз больше элементов. Таким образом, время поиска будет равно . Соответственно при честной монетке и уровней получаем оценку, полученную ранее. Для крайних распределений:
- —
- — (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе )
Удаление элемента
Алгоритм удаления достаточно тривиален.
- Найти удаляемый элемент
- Удалить его со всех уровней
Псевдокод
Наглядный, но не очень эффективный по памяти вариант списка с пропусками.
В узлах списка хранятся:
- — следующий узел
- — тот же узел на следующем уровне
- — данные типа T
- — ключ типа K
Вставка:
node insert (node i, K key, T data)
while i.key <= key // Ищем подходящее место
i = i.next()
node tmp = null // Для записи в поле down
if i.ref != null // Мы не на нижнем уровне
tmp = insert (i.ref, key) // Рекурсивный вызов на более низком уровне
if tmp == null // Проверка броска монетки
return null
i.next = new node (i.next, tmp, data, key) //Непосредственно вставка
if random(0,1) > 0.5 // Бросок монетки
return i.next // Нужно передать новый элемент для вставки выше
else
return null
void insert (list skip_list, K key, T data) // Обёрточка
insert(skip_list.head, key, data)
Удаление:
void erase (node i, K key)
if i == null
return
while i.key <= key // Ищем элемент
i = i.next()
erase(i.ref, key) // Удаляем с нижних уровней
if i.key == key // Если ключ совпадает
delete(i) // удаляем и с этого уровня
void erase (list skip_list, K key) // Обёрточка
erase(skip_list.head, key)
Применение
- Базы данных
- Распределённые вычисления и p2p
- Масштабируемые параллельные приоритетные очереди и словари
В вычислительной геометрии широко применяются структуры на основе списка с пропусками.
См. также
Структуры на основе списка с пропусками:
