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

Список с пропусками (skip list) — поисковая структура данных, позволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.

Поиск элемента в списке производится за [math]\Theta(\log(n))[/math]; добавление и удаление элемета происходит за то же время, что и поиск, однако эти операции могут замедлить поиск в структуре.

Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы.

Построение

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

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

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

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

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

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

1. Начинаем поиск элемента в верхнем списке ([math]L_k), рассмотрим первый элемент # Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу # Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска Пример поиска числа 8 в списке из описания: [[Файл:SkipListSearch.png]] Рассмотрим время работы для списка с двумя уровнями. Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне \lt tex\gt 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\lt tex\gt уровней, будет лучше всего работать с \lt tex\gt \sqrt[k]{n} [/math] элементами на уровне; время работы такого списка будет равно [math]k \sqrt[k]{n} [/math]. Для [math]\log_2{n}[/math] уровней же время работы составит [math] \log_2{n} \times \sqrt[\log{n}]{n} = n ^ {\frac{1}{log_2{n}}} \times \log{n} = n ^ {\log_n{2}} \times \log_2{n} = 2\log_2{n}[/math]

Пример поиска:

   T* find (list <node> skip_list, K key) {        // Возвращает собственно элемент
       node* pos = _find (skip_list, key);
       return pos->key == key ? pos : NULL;        // Вернёт элемент, если он есть, иначе NULL
   }

   node* _find (list <node> skip_list, K key) {    // Возвращает место элемента
       node * res;
       for (res = skip_list.begin(); res->ref != NULL; res = res->ref) {
           while (res->key <= key)                 // Переходим к следующему элементу (п. 2)
               res = res->next();
       }                                           // Спускаемся на шаг вниз, если можем (п. 3)
       return res;                                 // Возвращаем позицию элемента, либо (в случае отсутствия)
   }                                               // позицию, после которой его следует вставить

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

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

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[/math], [math]q[/math]}, математическое ожидание количества элементов на уровне [math]l[/math] равно [math]n q^l[/math], каждый уровень будет составлять [math]q[/math] от предыдущего; время поиска будет равно [math]O(\dfrac{k}{q} + nq^k)[/math]. Соответственно при честной монетке и [math]\log(n)\lt tex\gt уровней получаем оценку, полученную ранее. Для крайних распределений: * {\lt tex\gt 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

Конструктор 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) && (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);

См. также

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

Ссылки

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