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

После изучения алгоритма поиска узла в существующем списке с пропусками, давайте рассмотрим алгоритм построения списка с помощью операции вставки нового узла. Вернувшись к рисунку 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 выполняется проверка того, что мы не вышли за границы максимального уровня списка. Не имеет смысла создавать узел, который находится на намного более высоком уровне, нежели текущий максимальный уровень. Поэтому максимальное значение уровня ограничивается увеличением уровня на единицу.