Список с пропусками

Список с пропусками (англ. skip list) — структура данных, позволяющая в среднем за [math]O(\log(n))[/math] времени выполнять операции добавления, удаления и поиска элементов.

Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть [math]-[/math] на третьем и так далее, но при этом известно, что если элемент расположен на [math]i[/math]-ом уровне, то он также расположен на [math](i-1)[/math]-ом, [math](i-2)[/math]-ом и более низких уровнях.

Построение

Список с пропусками строится на основе существующего односвязного отсортированного списка.

Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять [math]O(\log(n))[/math].

Операции над структурой

Поиск элемента

Допустим, что в нашем списке с пропусками существуют [math]k[/math] уровней, при этом первым уровнем ([math]L_1[/math]) будет исходный список.

В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:

1. Начинаем поиск элемента в верхнем списке ([math]L_k[/math]), рассмотрим первый элемент
2. Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
3. Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска

Пример поиска числа [math]8[/math] в списке из описания:

Рассмотрим время работы для списка с двумя уровнями. Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне [math]L_2[/math]. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:

[math] \approx \vert L_2\vert + \dfrac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \dfrac{n}{\vert L_2\vert }[/math]

Минимизируя, мы получаем, что [math]\vert L_2 \vert ^ 2 = n[/math]

В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:

[math] \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}[/math]

Также можно убедиться, что список с пропусками, имеющий [math]k[/math] уровней, будет лучше всего работать с [math]\sqrt[k]{n} [/math] элементами на уровне; время работы такого списка будет равно [math]k \sqrt[k]{n} [/math]. Для [math]\log_2{n}[/math] уровней же время работы составит [math] \log_2{n} \cdot \sqrt[\log_2{n}]{n} = n ^ {\frac{1}{log_2{n}}} \cdot \log_2{n} = n ^ {\log_n{2}} \cdot \log_2{n} = 2\log_2{n}[/math]

Вставка элемента

Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:

1. Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
2. Вставить наш элемент в нижний уровень списка с пропусками
3. «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
4. Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат

Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется [math]\dfrac{n}{2}[/math], на третьем уровне [math]\dfrac{n}{4}[/math] и т.д. На уровне [math]\log{n}[/math] у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это [math]\dfrac{1}{2}[/math], на третий [math]\dfrac{1}{4}[/math] и т.д. Вероятность попасть на уровень [math]\log{n}[/math] равна [math]\dfrac{1}{n}[/math].

Используя монетку с распределением отличным от [math]\{\dfrac{1}{2}[/math], [math]\dfrac{1}{2}\}[/math], можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением [math]\{p,q\}[/math]}, математическое ожидание количества элементов на уровне [math]l[/math] равно [math]n q^l[/math], каждый уровень будет составлять [math]q[/math] от предыдущего; время поиска будет равно [math]O(\dfrac{k}{q} + nq^k)[/math]. Соответственно при честной монетке и [math]\log(n)[/math] уровней получаем оценку, полученную ранее. Для крайних распределений:

• [math]\{0, 1\}[/math] — [math]O(k+n)[/math]
• [math]\{1, 0\}[/math] — [math]\infty[/math] (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе [math]O(n)[/math])

Удаление элемента

Алгоритм удаления достаточно тривиален.

1. Найти удаляемый элемент
2. Удалить его со всех уровней

Псевдокод

Наглядный, но не очень эффективный по памяти вариант списка с пропусками.

В узлах списка хранятся:

• [math]next[/math] — следующий узел
• [math]down[/math] — тот же узел на следующем уровне
• [math]data[/math] — данные типа T
• [math]key[/math] — ключ типа 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
• Масштабируемые параллельные приоритетные очереди и словари

В вычислительной геометрии широко применяются структуры на основе списка с пропусками.

См. также

• Список
• Рандомизированное бинарное дерево поиска
• Поисковые структуры данных

Структуры на основе списка с пропусками:

• Skip quadtree: определение, время работы
• Википедия — Skip graph(En)

Источники информации

• Хабрахабр — Списки с пропусками
• Википедия — списки с пропусками(Ru)
• Википедия — списки с пропусками(En)
• Курс kiev-clrs — Списки с пропусками
• igoro.com — Skip lists are fascinating