Список с пропусками
Список с пропусками (англ. skip list) — структура данных, позволяющая в среднем за времени выполнять операции добавления, удаления и поиска элементов.
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на -ом уровне, то он также расположен на -ом, -ом и более низких уровнях.
Содержание
Построение
Список с пропусками строится на основе существующего односвязного отсортированного списка.
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять .
Операции над структурой
Поиск элемента
Допустим, что в нашем списке с пропусками существуют уровней, при этом первым уровнем () будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
- Начинаем поиск элемента в верхнем списке (), рассмотрим первый элемент
- Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
- Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска
Пример поиска числа в списке из описания:
В качестве примера рассмотрим список с двумя уровнями и . Поскольку элементы по уровням распределяются равномерно, то в среднем количество элементов между двумя соседними элементами уровня будет составлять . Оценим среднее время доступа к элементу. Мы пройдём не более элементов на втором уровне, однако, если на каком-нибудь шаге мы спустимся на нижней уровень, то пройдём в среднем не более элементов (в противном случае мы могли бы пройти ещё один элемент на втором уровне). Минимизируем величину . Очевидно, что при сумма достигает минимального значения. Таким образом, время поиска элемента составляет в среднем , отсюда выходит, что удаление и добавления элемента также происходит за , а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью .
Допустим, что у нас имеется не два, а уровней. Тогда оптимально на каждом из уровней проходить не более элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная .
Вставка элемента
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
- Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
- Вставить наш элемент в нижний уровень списка с пропусками
- «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
- Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется , на третьем уровне и т.д. На уровне у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это , на третий и т.д. Вероятность попасть на уровень равна .
Используя монетку с распределением отличным от , , можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением }, математическое ожидание количества элементов на уровне равно , каждый уровень будет составлять от предыдущего; время поиска будет равно . Соответственно при честной монетке и уровней получаем оценку, полученную ранее. Для крайних распределений:
- —
- — (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе )
Удаление элемента
Алгоритм удаления достаточно тривиален.
- Найти удаляемый элемент
- Удалить его со всех уровней
Псевдокод
Наглядный, но не очень эффективный по памяти вариант списка с пропусками.
В узлах списка хранятся:
- — следующий узел
- — тот же узел на следующем уровне
- — данные типа T
- — ключ типа K
Конструктор
list skip_list (list l):
list lvl = build_lvl(l) // Здесь происходит построение первого уровня
while lvl.size() > 2
lvl = build_lvl (lvl) // Добавление следующих уровней; последний содержит два элемента
return t
list build_lvl (list lvl) // Отсеивание нечётных элементов
list next_lvl
node i = lvl.head() // Перебор всех элементов lvl
while (i != null) and (i != lvl.tail())
next_lvl.push_back(node(i.key, i)) // Добавление чётного элемента;
i = i.next.next // он содержит ключ и ссылку на предыдущий уровень
return next_lvl
Поиск элемента по ключу:
T find (list skip_list, K key)
node res
for (res = skip_list.head; res.ref != null; res = res.ref)
// Cпускаемся на шаг вниз, если можем (п. 3)
while res.key <= key // Переходим к следующему элементу (п. 2)
res = res.next()
return res.data
Вставка:
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
- Масштабируемые параллельные приоритетные очереди и словари
В вычислительной геометрии широко применяются структуры на основе списка с пропусками.
См. также
Структуры на основе списка с пропусками:
