Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
TskNodeArray = array [0..pred(tdcMaxSkipLevels) ] of PskNode;
TskNode = packed record
sknData : pointer;
sknLevel : longint;
sknPrev : PskNode;
sknNext : TskNodeArray;
end;
Мы не собираемся объявлять переменные типа TskNode. Фактически мы будем иметь дело исключительно с переменными типа PskNode, память под которые выделяется из кучи. Размер переменной будет вычисляться как
(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 и т.д.
Алгоритм вставки в список с пропусками учитывает эти вероятности таким образом, чтобы в общем на каждом уровне находилось требуемое количество узлов. Это означает, что в среднем вероятностный список с пропусками будет работать с той же эффективностью, что и "однородный": поиск некоторых узлов будет осуществляться чуть дольше, а других - чуть быстрее, однако, в среднем, поиск в реальном списке с пропусками будет занимать примерно столько же времени, сколько и в идеальном однородном списке.
После такой теоретической подготовки можно перейти к описанию самого алгоритма вставки. Начинаем с пустого списка. Пустой список с пропусками содержит начальный узел уровня 11 и конечный узел уровня 0. Все прямые указатели начального узла указывают на конечный узел. Обратный указатель конечного узла указывает на начальный узел. Алгоритм вставки работает следующим образом:
1. Выполнить в списке поиск вставляемого элемента с одним дополнительным условием. При каждом понижении уровня сохранять значение переменной BeforeNode. В конце концов, мы получим набор значений BeforeNode, по одному для каждого уровня (поскольку количество уровней ограничено числом 12, для хранения уровней можно организовать простой массив из 12 элементов).
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 Кто-то может сказать, что узлы с равными значениями должны находиться в списке в том порядке, в котором они вставлялись. Это означает, что при вставке элемента он будет добавляться в конец последовательности узлов с равными значениями, а при поиске нужно будет находить первый из повторяющихся узлов. Для алгоритма вставки при понижении уровней нужно сохранять список "предыдущих узлов". Эту операцию выполнить сложнее. По мнению автора книги, излишняя сложность алгоритмов для обеспечения возможности хранения в списке с пропусками узлов с одинаковыми значениями себя совершенно не оправдывает. Будем считать, что если существует вероятность повторения узлов, то мы знаем, как их различать между собой. В противном случае, они будут трактоваться как действительно один и тот же узел. Если мы можем различать повторяющиеся узлы, то можно предположить, что такая же возможность заложена и в функции сравнения. Следовательно, узлы уже не будут считаться повторениями.
