Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

(3+sknLevel)*sizeof(pointer) + sizeof(longint)

Определившись со структурой узла списка с пропусками, можно перейти к рассмотрению реализации алгоритма поиска, которая приведена в листинге 6.15. Поиск представляет собой внутренний метод класса TtdSklpList. Он будет использоваться методами Add и Remove класса. И как мы сейчас увидим, еще одна его задач заключается в создании списка "предыдущих узлов" для каждого уровня.

Листинг 6.15. Поиск в списке с пропусками

function TtdSkipList.slSearchPrim(aItem : pointer;

var aBeforeNodes : TskNodeArray): boolean;

var

Level : integer;

Walker : PskNode;

Temp : PskNode;

CompareResult : integer;

begin

{заполнить весь массив BeforeNodes начальным узлом}

for Level := 0 to pred(tdcMaxSkipLevels) do

aBeforeNodes[Level] := FHead;

{инициализировать}

Walker := FHead;

Level := MaxLevel;

{начать поиск искомого узла}

while (Level >= 0) do

begin

{найти следующий узел на этом уровне}

Temp := Walker^.sknNext [Level];

{если следующий узел является конечным, считать его большим, чем искомый узел}

if (Temp = FTail) then

CompareResult := 1 {в противном случае сравнить данные следующего узла с искомыми данными}

else

CompareResult := FCompare(Temp^.sknData, aItem);

{если данные узла равны искомым данным, поиск завершен; выйти из функции}

if (CompareResult = 0) then begin

aBeforeNodes[Level] := Walker;

FCursor :=Temp;

Result := truer-Exit;

end;

{если данные следующего узла меньше, чем искомые данные, перейти в следующий узел}

if (CompareResult < 0) then begin

Walker := Temp;

end

{если данные следующего узла больше, чем искомые данные, понизить уровень}

else begin

aBeforeNodes[Level] := Walker;

dec(Level);

end;

end;

{если мы достигли этой точки, значит, искомый узел не найден}

Result := false;

end;

Реализация метода начинается с заполнения всего массива aBeforeNode начальным узлом. Затем поиск начинается с высшего уровня списка (MaxLevel). Переход по указателям высшего уровня продолжается до тех пор, пока не будет найден узел, данные которого больше искомых. Обратите внимание, что обрабатывается специальный случай для концевого узла. Предполагается, что данные конечного узла больше любых других данных в списке. К сожалению, для класса, предназначенного для любых типов данных, подобная проверка обязательна, поскольку значение конечного узла установить заранее невозможно. Если же, с другой стороны, разрабатывается список с пропусками специально для строк, значение конечного узла можно выбрать таким, чтобы оно было больше любой строки, которая будет храниться в списке.

После этого производится сравнение. Если данные равны, искомый узел найден, и после установки нескольких переменных выполнение метода завершается. Если данные узла меньше, чем искомые данные, осуществляется переход по прямому указателю. В противном случае текущий уровень записывается в массив aBeforeNode и значение уровня уменьшается на единицу.

После изучения алгоритма поиска узла в существующем списке с пропусками, давайте рассмотрим алгоритм построения списка с помощью операции вставки нового узла. Вернувшись к рисунку 6.3, можно сказать, что задача сохранения однородной структуры списка после серии выполнения вставок и удалений кажется практически невыполнимой.

Достоинство алгоритма вставки, разработанного Пью, заключается в том, что Пью понимал, что построение абсолютно однородной структуры списка, по сути дела, невозможно или, по крайней мере, является сложной и трудоемкой операцией. Поэтому он предложил список с пропусками, который в среднем приближается к однородной структуре. В однородном списке с пропусками с множителем 4 один из четырех узлов больше трех других, поскольку он содержит дополнительный прямой указатель. В свою очередь, один из четырех этих больших узлов содержит еще один дополнительный указатель и т.д. В конце концов, можно прийти к выводу, что в однородном списке с пропусками три четверти всех узлов находятся на уровне 0, три шестнадцатых - на уровне 1, три шестьдесят четвертых - на уровне 2 и т.д. Другими словами, при случайном выборе узла можно установить следующие вероятности выбора узлов по уровням:

0.75 для уровня 0,

0.1875 для уровня 1,

0.046875 для уровня 2 и т.д.

Алгоритм вставки в список с пропусками учитывает эти вероятности таким образом, чтобы в общем на каждом уровне находилось требуемое количество узлов. Это означает, что в среднем вероятностный список с пропусками будет работать с той же эффективностью, что и "однородный": поиск некоторых узлов будет осуществляться чуть дольше, а других - чуть быстрее, однако, в среднем, поиск в реальном списке с пропусками будет занимать примерно столько же времени, сколько и в идеальном однородном списке.