390
правок
Изменения
Нет описания правки
==Построение==
Допустим, что нам задан односвязный отсортированный список.
[[Файл:SimpleList.png]]
Тогда на самом нижнем <tex>L_1</tex>-ом первом уровне мы расположим все элементы списка в таком же порядкезаданный список, на <tex>L_2</tex>-ом втором <tex>-</tex> только элементы с чётными номерамис ссылками на соответствующие элементы первого уровня, на <tex>L_3</tex> третьем <tex>-</tex> с номерами , кратными <tex>4</tex> , и так далее. Такой список будет позволять в среднем за <tex>O(\log{n})</tex> выполнять операции поиска, добавления и удаления элементов.
[[Файл:SkipList.png]]
Функция <tex>\ \mathtt{buildLvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
'''list''' buildLvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font>
'''list''' nextLvl
'''node''' i = lvl.head() <font color=darkgreen>// Перебор всех элементов lvl</font>
'''while''' (i != ''null'') '''and''' (i != lvl.tail())
nextLvl.push_back(node(i.key, i)) <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font>
'''return''' nextLvl
Функция <tex>\ \mathtt{skipList} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
'''list''' skipList ('''list''' l):
'''list''' lvl = buildLvl(l) <font color=darkgreen>// Построение первого уровня</font>
'''while''' lvl.size() > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
lvl = buildLvl (lvl)
'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
==Операции над структурой==
* <tex>key</tex> {{---}} ключ типа K
Поиск элемента по ключу:
<code>
