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

Списки с пропусками

Списки с пропусками

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

Код класса для списков с пропусками можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSkpLst.pas.

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

Вильям Пью (William Pugh) в 1990 году в своей статье "Списки с пропусками: вероятностная альтернатива сбалансированным деревьям" ("Skip Lists: Probabilistic AItemative to Balanced Trees") [18] показал, что существует более удобная альтернатива связным спискам, если мы готовы использовать узлы большего размера с большим количеством указателей.

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

Из рисунка видно, что при поиске значения с использованием новых указателей, мы переходим сначала большими шагами, постепенно уменьшая размер "прыжков", пока искомое значение не будет найдено. Буквально через несколько параграфов процесс поиска будет описан более подробно.

Рисунок 6.3. Схематичное представление списка с пропусками

Оглавление книги