390
правок
Изменения
→Построение
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементаэлементы, номера которых кратны четырём. Аналогично Аналогичным образом построим и последующие уровни.
====Псевдокод====
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
Элементы односвязного списка состоят из вершин <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:* <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент списка* <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>.
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
'''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font>
'''list''' next_lvl
'''node''' i = lvl.head() <font color=darkgreen>// Перебор всех элементов lvl</font> '''while''' (i != ''null'') '''and''' (i != lvl.tail())
next_lvl.push_back(node(i.key, i)) <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font>
'''list''' skip_list ('''list''' l):
'''list''' lvl = build_lvl(l) <font color=darkgreen>// Построение первого уровня</font>
'''while''' lvl.size() > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font> lvl = build_lvl (lvl)
'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
