Изменения

Допустим, что нам задан односвязный отсортированный списоки мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.

Тогда на первом На самом нижнем уровне списка с пропусками мы расположим заданный исходный список, на . На втором уровне <tex>-</tex> только всё элементы с чётными номерами с ссылками , причём каждый элемент будет ссылаться на соответствующие элементы первого уровня, соответствующий ему элемент на третьем <tex>-</tex> с номераминижнем уровне. Таким же образом построим и третий уровень, кратными <tex>4</tex>куда будем добавлять только те элемента, и так далееномера которых кратны четырём. Такой список будет позволять в среднем за <tex>O(\log{n})</tex> выполнять операции поиска, добавления Аналогично построим и удаления элементовпоследующие уровни. 

Функция <tex>\ \mathtt{buildLvlbuild\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.

'''list''' buildLvl build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> '''list''' nextLvl next_lvl

nextLvlnext_lvl.push_back(node(i.key, i)) <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>

'''return''' nextLvl next_lvl

Функция <tex>\ \mathtt{skipListskip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.

'''list''' skipList skip_list ('''list''' l): '''list''' lvl = buildLvlbuild_lvl(l) <font color=darkgreen>// Построение первого уровня</font> '''while''' lvl.size() > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font> lvl = buildLvl build_lvl (lvl) '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>