2. Если искомый элемент найден, вызвать ошибку (мы скоро скажем, по какой причине) и остановиться.
3. Узел не найден. Как уже упоминалось, нам известно, между каким узлами необходимо вставить новый элемент. Кроме того, при поиске мы достигли уровня 0.
4. Установить значение переменной NewNode равным нулю.
5. С помощью генератора случайных чисел вычислить случайное число в диапазоне от 0 до 1.
6. Если случайное число меньше 0.25, увеличить значение переменной NewNode на единицу.
7. Если значение переменной NewNode меньше или равно текущему максимальному уровню списка (т.е. 11), вернуться к шагу 5.
8. Если значение переменной NewNode больше текущего максимального уровня списка, присвоить ей значение максимального уровня плюс один.
9. Создать узел уровня NewNode и установить его указатель данных на вставляемый элемент.
10. Теперь новый узел нужно учесть во всех указателях вплоть до уровня NewNode (именно поэтому мы записывали все значения переменной BeforeNode при поиске на шаге 1). Для этого выполняется алгоритм "вставить после" для двухсвязного списка на уровне 0 и для всех односвязных списков для уровней от 1 до NewNode.
В приведенном алгоритме существуют несколько "странных" шагов, которые требуют дополнительных объяснений. Так, например, шаги 5, 6, 7 и 8, на которых вычисляется значение переменной NewNode, - для чего они нужны? Прежде всего, здесь вычисляется размер нового узла. Как вы, наверное, помните, мы пытаемся создать список с требуемым количеством узлов каждого уровня. Узел уровня 0 должен создаваться в трех четвертях всех случаев, узел уровня 1 - в трех шестнадцатых всех случаев и т.д. Эти вычисления выполняются в цикле на шагах 5, 6 и 7. Во-вторых, на шаге 8 выполняется проверка того, что мы не вышли за границы максимального уровня списка. Не имеет смысла создавать узел, который находится на намного более высоком уровне, нежели текущий максимальный уровень. Поэтому максимальное значение уровня ограничивается увеличением уровня на единицу.
Шаг 2 также заслуживает отдельного рассмотрения. Фактически, в нем утверждается, что в списке с пропусками не могут храниться повторяющиеся элементы или, если выражаться более строго, элементы, в результате сравнения которых получается равенство. Почему? Представьте себе, что имеется список с пропусками, содержащий 42 узла, все значения которых равны а. В таком случае, что будет означать фраза: "Поиск узла а"? Учитывая саму природу списка с пропусками, на первом шаге поиска при переходе, скажем, на узел 35 будет найдено искомое значение а. Очевидно, что оно не будет ни первым в списке, ни последним - просто одним из 42 имеющихся в списке. Нужно ли в алгоритм вводить прохождение списка в обратном направлении, пока не будет найден первый узел со значением al Кто-то может сказать, что узлы с равными значениями должны находиться в списке в том порядке, в котором они вставлялись. Это означает, что при вставке элемента он будет добавляться в конец последовательности узлов с равными значениями, а при поиске нужно будет находить первый из повторяющихся узлов. Для алгоритма вставки при понижении уровней нужно сохранять список "предыдущих узлов". Эту операцию выполнить сложнее. По мнению автора книги, излишняя сложность алгоритмов для обеспечения возможности хранения в списке с пропусками узлов с одинаковыми значениями себя совершенно не оправдывает. Будем считать, что если существует вероятность повторения узлов, то мы знаем, как их различать между собой. В противном случае, они будут трактоваться как действительно один и тот же узел. Если мы можем различать повторяющиеся узлы, то можно предположить, что такая же возможность заложена и в функции сравнения. Следовательно, узлы уже не будут считаться повторениями.
В листинге 6.16 приведена реализация метода Add для класса списка с пропусками. В качестве генератора случайных чисел используется минимальный стандартный генератор, который мы изучали в первой части главы. Во всем остальном реализация следует алгоритму, описанному выше.
Листинг 6.16. Вставка в список с пропусками
procedure TtdSkipList.Add(aItem : pointer);
var
i, Level : integer;
NewNode : PskNode;
BeforeNodes : TskNodeArray;
begin
{выполнить поиск узла и заполнить значениями массив BeforeNodes}
if slSearchPrim(aItem, BeforeNodes) then
slError(tdeSkpLstDupItem, 'Add');
{вычислить уровень для нового узла}
Level := 0;
while (Level <= MaxLevel) and (FPRNG.AsDouble < 0.25) do inc(Level);
{если мы вышли за границы максимального уровня, сохранить новое значение в качестве максимального уровня}
if (Level > MaxLevel) then
inc(FMaxLevel);
{выделить память для нового узла}
NewNode := slAllocNode(Level);
NewNode^.sknData := aItem;
{восстановить указатели для уровня 0 - двухсвязный список}
NewNode^.sknPrev := BeforeNodes[0];
NewNode^.sknNext[0] := BeforeNodes[0]^.sknNext[0];
BeforeNodes[0]^.sknNext[0] := NewNode;
NewNode^.sknNext[0]^.sknPrev := NewNode;
{восстановить указатели для других уровней - односвязные списки}
for i := 1 to Level do
begin
NewNode^.sknNext[i] := BeforeNodes[i]^.sknNext[i];
BeforeNodes[i]^.sknNext[i] := NewNode;
end;
{теперь в список с пропусками добавлен новый узел}
inc(FCount);
end;
Обратите внимание, что проверка в самом начале метода необходима для того, чтобы убедиться, что в списке не будет повторяющихся элементов. Кроме того, наличие повторяющихся элементов существенно уложило бы операцию удаления.
Алгоритм удаления узла из списка с пропусками достаточно прост, несмотря на его длину. Он выглядит следующим образом:
1. Найти удаляемый узел с помощью обычного алгоритма поиска.
2. Предположим, что узел находится на уровне i. Сохранить узел, расположенный перед удаляемым и находящийся на том же уровне, что и i-тый элемент в массиве. Установить значение переменной LevelNumber равным i, а предыдущий узел записать в переменную BeforeNode.