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

Упражнения

> 13.48 Нарисуйте RB-дерево бинарного поиска, образованное в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустое дерево с использованием метода нисходящей вставки.

> 13.49 Нарисуйте RB-дерево бинарного поиска, образованное в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустое дерево с использованием метода восходящей вставки.

о 13.50 Нарисуйте RB-дерево, образованное в результате вставки по порядку букв от А до К в первоначально пустое дерево, а затем опишите, что происходит в общем случае построения дерева путем вставки ключей в порядке возрастания.

13.51 Приведите последовательность вставок, в результате которой будет создано RB-дерево на рис. 13.16.

13.52 Создайте два произвольных 32-узловых RB-дерева. Нарисуйте их (вручную или с помощью программы). Сравните их с BST-деревьями (несбалансированными), построенными из этих же ключей.

13.53 Сколько различных RB-деревьев соответствуют 2-3-4-дереву, содержащему / 3-узлов?

о 13.54 Нарисуйте все структурно различные RB-деревья поиска, содержащие N ключей, при 2 < < 12.

13.55 Определите вероятность того, что каждое из деревьев в упражнении 13.43 является результатом вставки iV случайных различных элементов в первоначально пустое дерево.

13.56 Создайте таблицу, в которой приведено количество деревьев для каждого значения из упражнения 13.54, являющихся изоморфными в том смысле, что они могут быть преобразованы одно в другое путем взаимной замены поддеревьев в узлах.

13.57 Покажите, что в худшем случае длина почти всех путей от корня к внешнему узлу в RB-дереве, состоящем из N узлов, равна 2 IgjV.

13.58 Сколько ротаций требуется в худшем случае для вставки в RB-дерево, состоящее из N узлов?

о 13.59 Используя RB-представление и рекурсивный подход, аналогичный программе 13.6, реализуйте операции construct, search и insert ддя таблиц символов, в основе которых лежат структуры данных в виде восходящих сбалансированных 2-3-4-деревьев. Совет: код может выглядеть аналогично программе 13.6, но должен выполнять операции в другом порядке.

13.60 Используя RB-представление и рекурсивный подход, аналогичный программе 13.6, реализуйте операции construct, search и insert для таблиц символов, в основе которых лежат структуры данных в виде восходящих сбалансированных 2-3-де-ревьев.

13.61 Используя рекурсивный подход, аналогичный программе 13.6, реализуйте операции construct, search и insert для таблиц символов, в основе которых лежат структуры данных в виде сбалансированных по высоте (AVL) деревьев.

13.62 Измените реализацию, созданную в упражнении 13.61, чтобы использовать RB-деревья (содержащие по 1 разряду на узел) для кодирования информации о балансировке.

13.63 Реализуйте сбалансированные 2-3-4-деревья, используя представление RB-дерева, в котором 3-узлы всегда наклонены вправо. Примечание: это изменение позволяет исключить из внутреннего цикла операции insert одну из проверок разрядов.

13.64 Для сохранения сбалансированности 4-узлов программа 13.6 выполняет ротации. Разработайте использующую представление в виде RB-дерева реализацию сбалансированных 2-3-4-деревьев, в которой 4-узлы могут быть представлены любыми тремя узлами, соединенными двумя R-связями (полностью сбалансированными или несбалансированными).

о 13.65 Не прибегая к использованию дополнительного объема памяти для хранения разряда цвета, реализуйте операции construct, search и insert для RB-деревьев, воспользовавшись следующим приемом. Чтобы окрасить узел в красный цвет, поменяйте местами две его связи. Затем, чтобы проверить, является ли узел красным, проверьте, больше ли его левый дочерний узел, чем правый. Дабы обеспечить возможный обмен указателями, придется модифицировать функции сравнения; в результате использования такого приема сравнения разрядов заменяются сравнениями ключей, что, по всей вероятности, требует больших затрат, однако метод демонстрирует, что в случае необходимости можно избавиться от дополнительного разряда в узлах.

13.66 Реализуете нерекурсивную функцию вставки в RB-дерево бинарного поиска (см. программу 13.6), которая соответствует вставке в сбалансированное 2-3-4-дерево в течение одного прохода. Совет: введите связи gg, g и р, которые указывают, соответственно, на прадеда, деда и родителя текущего узла в дереве. Все эти связи могут Потребоваться для выполнения двойной ротации.

13.67 Создайте программу, которая вычисляет процентную долю В-узлов в заданном RB-дереве бинарного поиска. Протестируйте программу, вставив N случайных ключей в первоначально пустое дерево, при yV = 10 , IO *, 10 и 10.

13.68 Создайте программу, которая вычисляет процент элементов, находящихся в 3-узлах и 4-узлах заданного 2-3-4-дерева поиска. Протестируйте программу, вставив Лслучайных ключей в первоначально пустое дерево, при = 10, 10 *, 10 и 10

О 13.69 Используя по одному разряду на узел для представления цвета, можно представлять 2-, 3- и 4-узлы. Сколько разрядов на узел потребовалось бы для представления бинарным деревом 5-, 6- и 7-узлов?

13.70 Эмпирически вычислите среднее значение и стандартное отклонение количества сравнений, используемых для выявления попаданий и промахов при поиске в RB-дереве, построенном в результате вставки Л случайных узлов в первоначально пустое дерево, при N = 10, Ю , 10 и 10.

13.71 Модифицируйте программу, созданную в упражнении 13.70, для вычисления количества ротаций и разделений узлов, используемых для построения деревьев. Проанализируйте полученные результаты.

13.72 Воспользуйтесь программой-драйвером из упражнения 12.30 для сравнения свойства самоорганизации расширенных BST-деревьев с гарантиями, обеспечиваемыми RB-деревьями бинарного поиска для худшего случая и со стандартными BST-деревьями для распределений запросов на поиск, определенных в упражнениях 12.31 и 12.32 (см. упражнение 13.29).

13.73 Реализуйте функцию search для RB-деревьев, которая выполняет ротации и изменяет цвета узлов в процессе спуска по дереву с целью обеспечения того, что узел в нижней части пути поиска не является 2-узлом.

13.74 Воспользуйтесь решением упражнения 13.73 для реализации функции remove для RB-деревьев. Найдите узел, который должен быть удален, продолжите поиск вплоть до нахождения 3-узла или 4-узла в нижней части пути и переместите узел-наследник из нижней части, чтобы заменить удаленный узел.

13.5 Списки пропусков

В этом разделе мы рассмотрим подход к разработке быстрых реализаций операций с таблицами символов, которые на первый взгляд кажутся совершенно отличными от рассмотренных методов, основанных на использовании деревьев, но в действительности очень тесно связанных с ними. Подход основан на рандомизованной структуре данных и почти наверняка обеспечивает практически оптимальную производительность всех базовых операций для АТД таблиц символов. Лежашая в основе алгоритма структура данных, которая была разработана Пухом (Pugh) в 1990 г. {см. раздел ссылок), называется списком пропусков. В ней дополнительные связи в узлах связного списка используются для пропуска больших частей списка во время поиска.

На рис. 13.22 приведен простой пример, в котором третий узел в упорядоченном связном списке содержит дополнительную связь, которая позволяет пропустить три узла списка. Дополнительные связи можно использовать для ускорения операции search: просмотр верхней части списка выполняется до тех пор, пока не будет найден ключ или узел с меньшим ключом, содержащий связь с узлом с большим ключом; затем связи в нижней части используются для проверки двух промежуточных узлов. Этот метод ускоряет выполнение операции search в три раза, поскольку в ходе успешного поиска к-то узла в списке исследуются лишь около к/Ъ узлов.

РИСУНОК 13.22 ДВУХУРОВНЕВЫЙ СВЯЗНЫЙ СПИСОК

Каждый третий узел в этом списке содержит вторую связь, поэтому можно выполнять пропуски в списке и почти в три раза ускорить прохождение по списку по сравнению с использованием только первых связей. Например, до двенадцатого узла в списке (Р), можно добраться из начала списка, следуя лишь по пяти связям: вторым связям к С, G, L, N, а затем по первой связи узла N к Р.