Упражнения

13.75 Нарисуйте список пропусков, образованный в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустой список, если считать, что randX возвращает последовательность значений 1,3, 1, 1, 2, 2, 1, 4, 1 и 1.

о 13.76 Нарисуйте список пропусков, образованный в результате вставки элементов с ключами EAINOQSTUYb указанном порядке в первоначально пустой список, если считать, что функция randX возвращает такие же значения, как и в упражнении 13.75.

13.77 Реализуйте операцию select для таблицы символов на базе списка пропусков.

13.78 Реализуйте операцию join для таблицы символов на базе списка пропусков.

о 13.79 Модифицируйте реализации операций search и insert, приведенные в программах 13.7 и 13.9, чтобы вместо нулевых они создавали списки с сигнальными узлами.

о 13.80 Задействуйте списки пропусков при реализации операций construct, search и insert для таблиц символов, использующих абстракцию сбалансированного 2-3-4-дерева.

о 13.81 Сколько случайных чисел требуется в среднем для построения списка пропусков с параметром /, с использованием функции randX() из программы 13.9?

о 13.82 Для t = 2 измените программу 13.9 так, чтобы исключить цикл for из функции randX. Совет: последние j разрядов в бинарном представлении числа t принимают значение любого отдельного разряда j с вероятностью 1/2

133 Выберите значение г, которое минимизирует затраты на поиск для случая, когда затраты на следование по связи в а раз превышают затраты на выполнение сравнения, а затраты на выполнение перехода на один уровень рекурсии вниз в Д раз превышают затраты на выполнение сравнения.

о 13.84 Разработайте реализацию списка пропусков, в которой узлы содержат сами указатели, а не указатель на массив указателей, который использовался в про-фаммах 13.7 - 13.10. Совет: поместите массив в конец узла.

13.6 Характеристики производительности

Как для конкретного приложения произвести выбор между рандомизованными BST-деревьями, расширенными BST-деревьями, RB-деревьями бинарного поиска и списками пропусков? Дол сих пор внимание было сосредоточено на различной природе гарантий производительности, обеспечиваемых этими алгоритмами. Время и занимаемый объем памяти всегда являются главным определяющим фактором, но необходимо учитывать также и ряд других факторов. В этом разделе мы кратко рассмотрим вопросы реализации, эмпирические иса1едования, оценку времени выполнения и требования к объему памяти.

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

Из трех основанных на деревьях алгоритмов проще всего реализовать рандомизованные BST-деревья. Главные требования - надежность генератора случайных чисел и избежание слишком больших затрат времени на генерирование случайных разрядов. Расширенные деревья несколько более сложны, но являются простым расширением стандартного алгоритма вставки в корень. RB-деревья бинарного поиска требуют еще большего объема кода для проверки и манипулирования разрядами цвета. Одно из преимуществ RB-деревьев по сравнению двумя другими алгоритмами - возможность использования разрядов цвета для проверки логики при отладке и для обеспечения быстрого поиска в любой момент времени в течение времени жизни дерева. Исследуя расширенное BST-дерево, невозможно выяснить, все ли необходимые преобразования выполняет создающий его код; программная ошибка может приводить (только!) к проблемам, связанным с производительностью. Аналогично, ошибка в генераторе случайных чисел, используемом для рандомизованных BST-деревьев или списков пропусков, может привести к незамеченным в противном случае проблемам производительности.

Списки пропусков легко реализовать и они особенно привлекательны, если требуется поддерживать полный набор операций для таблиц символов, поскольку все операции search, insert, remove, join, select и sort имеют естественные реализации, которые легко сформулировать. Внутренний цикл для выполнения поиска в списках пропусков длиннее, чем в деревьях (для него требуется дополнительный индекс в массиве указателей или дополнительный рекурсивный вызов для перемещения на нижний уровень), поэтому время поиска и вставки удлиняется. Кроме того, списки пропусков ставят программиста в зависимость от генератора случайных чисел, поскольку отладка программы, поведение которой носит случайный характер, - весьма сложная задача, и некоторые программисты особенно не любят работать с узлами, содержащими случайное количество связей.

В табл. 13.1 приведены экспериментальные данные по производительности четырех рассмотренных в этой главе методов, а также реализаций элементарных BST-деревьев, описанных в главе 12, для ключей, которые являются случайными 32-разрядными целыми числами. Приведенные в этой таблице данные подтверждают аналитические результаты, полученные в разделах 13.2, 13.4 и 13.5. RB-деревья работают со случайными ключами гораздо быстрее других алгоритмов. Пути в них на 35 процентов короче, чем в рандомизованных или расширенных BSR-деревьях, в во внутреннем цикле приходится выполнять меньший объем работы. Рандомизованные деревья и списки пропусков требуют генерации, по меньшей мере, одного случайного числа для каждой вставки, а расширенные BST-деревья сопряжены с ротацией в каж-

дом узле во время выполнения вставки и поиска. И наоборот, накладные расходы при использовании RB-деревьев бинарного поиска заключаются в том, что для каждой вставки приходится проверять значение 2 разрядов в каждом узле, а иногда приходится выполнять и ротацию. При неравномерном доступе расширенные BST-деревья могут обеспечивать более короткие пути, но эта экономия, скорее всего, будет сводится на нет тем, что и для поиска, и для вставки требуются ротации в каждом узле во внутреннем цикле, за исключением, быть может, экстремальных случаев.

Таблица 13.1 Результаты экспериментального изучения реализаций

сбалансированных деревьев

Эти сравнительные значения времени построения и поиска в BST-деревьях, образованных случайными последовательностями N 32-разрядных чисел, при различных значениях N, показывают, что все методы обеспечивают хорошую производительность даже для очень больших таблиц, но RB-деревья работают значительно быстрее других методов. Во всех методах используется стандартный поиск в BST-дереве, за исключением расширенных BST-деревьев, где при поиске выполняется расширение с целью перемещения часто посещаемых узлов ближе к вершине, и списков пропусков, в которых используется, по сути дела, этот же алгоритм, но по отношению к другой структуре данных.

конструирование

промахи при поиске

Обозначения: В Т R S С L

Стандартное BST-дерево (программа 12.8)

BST-дерево, построенное при помощи вставок в корень (программа 12.13) Рандомизованное BST-дерево (программа 13.2) Расширенное BST-дерево (упражнение 13.33 и программа 13.5) RB-дерево бинарного поиска (программа 13.6) Список пропусков (программы 13.7 и 13.9)

Расширенные BST-деревья не требуют использования дополнительного объема памяти под информацию о балансировке; RB-деревья бинарного поиска требуют 1 дополнительного разряда; рандомизованные BST-деревья требуют наличия поля счетчика. Для многих приложений поле счетчика поддерживается по ряду других причин, поэтому оно может быть и не сопряжено с дополнительными затратами для рандомизованных BST-деревьев. Действительно, добавление этого поля может потребоваться