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

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

Отсортированный связный список является простейшей структурой со временем поиска [math]\theta(n)[/math]. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.

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

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

Допустим, что в нашем списке с пропусками существуют два уровня: [math]L_1[/math], в котором содержатся все элементы и [math]L_2[/math], в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.

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

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

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

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

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

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

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

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

• Для трех уровней: [math] 3 \sqrt[3]{n}[/math]
• Для четырех уровней: [math] 4 \sqrt[4]{n}[/math]
• Для пяти уровней: [math] 5 \sqrt[5]{n}[/math]
• Для [math]\log{n}[/math] уровней: [math] \log{n} \sqrt[\log{n}]{n} = 2 \log{n}[/math]

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

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

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

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

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

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

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

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

Псевдокод

 const float P = 0.5
 
 int random_level()
     int lvl = (int)(log(frand())/log(1.-P))
     return lvl < MAX_LEVEL ? lvl : MAX_LEVEL
 
 
 boolean Find (int key)
 	SkipNode x = header
     for (int i = level; i >= 0; i--)
 		while (x.forward[i] != NULL && x.forward[i].value < key)
 			x = x.forward[i]
 	x = x.forward[0]
     return x != NULL && x.value == key
 	
 	
 	
 
 void Insert(int value) 
     SkipNode x = header
     SkipNode update
     update.assign(MAX_LEVEL + 1, 0)
 	
     for (int i = level; i >= 0; i--) 
 		while (x.forward[i] != NULL && x.forward[i].value < value)
 			x = x.forward[i]
 		update[i] = x
 	x = x.forward[0]
     if (x == NULL || x.value != value)        
         int lvl = random_level()
         if (lvl > level)
 			for (int i = level + 1; i <= lvl; i++)
 				update[i] = header
 			level = lvl
         x = new SkipNode(lvl, value)
 		for (int i = 0; i <= lvl; i++)
 			x.forward[i] = update[i].forward[i]
 			update[i].forward[i] = x
 			
 			
 void Erase(int value)
     SkipNode x = header
     SkipNode update
 	update.assign(MAX_LEVEL + 1, 0)
     for (int i = level; i >= 0; i--) 
 		while (x.forward[i] != NULL && x.forward[i].value < value)
 			x = x.forward[i]
 		update[i] = x
 	x = x.forward[0]
     if (x.value == value)
         for (int i = 0; i <= level; i++)
 			if (update[i].forward[i] != x)
 				break
 			update[i].forward[i] = x.forward[i];
         delete x
         while (level > 0 && header.forward[level] == NULL)
 			level--




Ссылки

• Хабрахабр — Списки с пропусками
• Википедия — списоки с пропусками(Ru)
• Википедия — списки с пропусками(En)
• Курс kiev-clrs — Списки с пропусками