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

Определение 13.5 Список пропусков (skip list - это связный список, в котором каждый узел содержит различное количество связей, причем i-тые связи в узлах реализуют односвязные списки, пропускающие узлы, содержащие менее чем i связей.

На рис. 13.23 показан этот же список пропусков и приведен пример поиска и вставки нового узла. Для выполнения поиска можно выполнить просмотр в верхнем списке, пока не будет найден ключ поиска или узел с меньшим ключом, содержащий связь с узлом с большим ключом. Затем мы переходим ко второму сверху списку и повторяем процедуру, продолжая этот процесс, пока не будет найден ключ поиска или пока в нижнем уровне не будет обнаружен промах при поиске. Для вставки мы выполняем поиск, связываясь с новым узлом при переходе с уровня к на уровень к-1, если новый узел содержит, по меньшей мере. А; дополнительных связей.

Внутреннее представление узлов предельно простое. Единственная связь в одно-связном списке заменяется массивом связей и целочисленной переменной, содержащей количество связей в узле. Управление памятью - вероятно, наиболее сложный аспект использования списков пропусков. Объявления типов и код для выделения памяти под новые узлы будут вскоре исследованы при рассмотрении вставки. Пока же достаточно отметить, что доступ к узлу, который следует за узлом t на (А; + 1-м) уровне списка пропусков, можно получить так: t->next[k]. Рекурсивная реализация в программе 13.7 демонстрирует, что поиск в списках пропусков не только является весь-

-±

b а И

ID tU tH

n1 ш

РИСУНОК 13.23 ПОИСК и ВСТАВКА В СПИСКЕ ПРОПУСКОВ

Добавляя дополнительные уровни к структуре, показанной на рис. 13.22, и позволяя связям пропускать различное количество узлов, мы получаем пример обобщенного списка пропусков. Для поиска ключа в этом списке процесс начинается с самого верхнего уровня с переходом вниз при каждой встрече ключа, который не меньше ключа поиска. В данном случае (см. верхний рисунок) мы находим ключ L, начав с уровня 3, следуя вдоль первой связи, затем спускаясь к G (считая нулевую связь связью со служебным узлом), затем следуя к I, спускаясь к уровню 2, поскольку S больше чем L, затем спускаясь к уровню 1, поскольку Мбольше L. Для вставки узла L с тремя связями мы связываем его с тремя списками именно там, где во время поиска были найдены связи с большими ключами.

ма понятным обобщением поиска в односвязных списках, но и подобен бинарному поиску или поиску в BST-деревьях. Вначале проверяется, содержит ли текущий узел ключ поиска. Затем, если это не так, ключ в текущем узле сравнивается с ключом поиска. Если он больше, выполняется один рекурсивный вызов, а если меньше - другой.

Программа 13.7 Поиск в списках пропусков

Для к равного О этот код эквивалентен программе 12.6, выполняющей поиск в односвязных списках. Для общего случая к мы переходим к следующему узлу на уровне к списка, если его ключ меньше ключа поиска, и вниз к уровню к-1, если его ключ меньше.

private:

Item searchR (link t, Key v, int k) {if (t = 0) return nullltem;

if (v =s= t->item.key 0) return t->item; link X = t->next[k];

if ((X == 0) II (V < x->item.key())) {

if (k == 0) return nullltem; return searchR(t, v, k-1) ;

return searchR (x, v, k) ;

public: Item search (Key v)

{ return searchR(head, v, IgN); }

Первой задачей, с которой мы сталкиваемся при необходимости вставки нового узла в список пропусков, является определение количества связей, которые должен содержать узел. Все узлы содержат, по меньшей мере, одну связь; следуя интуитивному представлению, отображенному на рис. 13.22, на втором уровне можно пропускать сразу по / узлов, если один из каждых / узлов содержит, по меньшей мере, две связи; применяя итеративный подход, мы приходим к заключению, что один из каждых узлов должен содержать по меньшей мере j + 1 связей.

Для создания узлов, обладающих таким свойством, мы выполняем рандомизацию, используя функцию, которая возвращает у + 1 с вероятностью \/г\ Имея j, мы создаем новый узел с j связями и вставляем его в список пропусков, используя ту же рекурсивную схему, которую использовали для выполнения операции search, как показано на рис. 13.23. После достижения уровня j мы связываем новый узел при каждом спуске на следующий уровень. К этому моменту уже установлено, что элемент в текущем узле меньше ключа поиска и связан (на уровне j) с узлом, который не меньше ключа поиска.

Для инициализации списка пропусков мы строим заглавный узел с максимальным количеством уровней, которые будут разрешены в списке, и нулевыми указателями на всех уровнях. Программы 13.8 и 13.9 реализуют инициализацию и вставку для списков пропусков.

Программа 13.8 Структуры данных и конструктор списка пропусков

Узлы в списках пропусков содержат массив связей, поэтому конструктор для node должен распределить массив и установить все связи в 0. Константа IgNmax - максимальное количество уровней, которые разрешаются в списке: ее значение может быть установлено равным пяти для крошечных списков или 30 - для огромных. Переменная N, как обычно, хранит количество элементов в списке, а IgN - количество уровней. Пустой список является заглавным узлом с IgNmax связей, которые все установлены в О, при нулевых N и IgN.

private: struct node

{ Item item; node **next; int sz; node (Item x, int k)

{ item = x; sz = k; next = new node*[k];

for (int i = 0; i < k; i++) next[i] =0; }

typedef node *link; link head; Item nullltem; int IgN; public: ST(int)

{ head = new node (nullltem, IgNmax); IgN = 0; }

Программа 13.9 Ваавка в список пропусков

Мы генерируем новый у-связный узел с вероятностью 1/2 затем перемещаемся вдоль пути поиска точно так же, как программе 13.7, но связываем новый узел при переходе на каждый из расположенных ниже у уровней.

private: int randXO

{ int i, j, t = rand () ;

for (i = 1, j = 2; i < IgNmax; i++, j += j)

if (t > RAND MAX/j) break; if (i > IgN) IgN = i; return i;

void insertR(link t, link x, int k)

{ Key V = x->item.key0 ; link tk = t->next[k]; if ((tk ==0) II (V < tk->item.key())) {

if (k < x->sz)

{ x->next[k] = tk; t->next[k] = x; } if (k = 0) return; insertR(t, X, k-1); return;

insertR(tk, x, k);

p;iblic: void insert(Item v)

{ insertR(head, new node(v, randX()), IgN); }

Ha рис. 13.24 демонстрируется построение списка пропусков для тестового набора ключей, вставляемых в случайном порядке; на рис. 13.25 приведен более объемный