рует бинарное дерево, содержащее те же элементы. Предположим, чтй ключ, расположенный в элементе, занимает k слов и каждая ссыпи занимает одно слово памяти. Какова будет экономия памяти при цс. пользовании бинарного дерева по сравнению с -арным?

4.15. Предположим, что дерево построено на основе следующего описания рекурсивной структуры данных (см. упр. 4.1):

rectype free = record х: integer,

left, right: tree

Сформулируйте процедуру, которая находит элемент с заданным ключом x и выполняет операцию Р с этим элементом.

4.16. В файловой системе каталог файлов организован в виде упорядоченного бинарного дерева. Каждый узел обозначает файл и содержит имя файла, а также среди прочего дату последнего обращения к нему, закодированную в виде целого числа.

Напишите программу, которая обходит дерево и удаляет все файлы, последнее обращение к которым происходило до определенной даты.

4.17. В некоторой древовидной структуре частота обращения к каждому элементу измеряется эмпирически - приписыванием каждому узлу счетчика обращений. Через определенный интервал времени организация дерева изменяется при помощи обхода всего дерева и формирования нового дерева с использованием программы 4.4, которая вставляет элементы в порядке убывания счетчиков частоты обращений. Напишите программу, которая выполняет эту реорганизацию. Будет ли средняя длина пути в этом дереве равна, хуже или намного хуже, чем в оптимальном дереве?

4.18. Метод анализа алгоритма включения в дерево, описанный в разд. 4.5, можно также использовать для вычисления средних значений для числа сравнений С„ и числа пересылок (обменов) Мп, которые выполняются с помощью алгоритма быстрой сортировки (программа 2.10) при обработке п элементов массива, считая, что все п\ перестановок п ключей {I, 2, п] равновероятны. Найдите аналогию и определите Сп и М„,

4.19. Нарисуйте сбалансированное дерево с 12 узлами, имеющее максимальную высоту среди всех сбалансированных деревьев с 12 узлами. В какой последовательности нужно включать узлы, чтобы процедура (4.63) сформировала это дерево?

4.20. Найдите такую последовательность из п включаемых элементов, чтобы процедура (4.63) выполняла каждое из четырех действий балансировки (LL, RR, RL, LR) по крайней мере один раз. Какова минз-мальная длина такой последовательности?

4.21. Найдите сбалансированное дерево с ключами 1... и перестановку этих ключей, такие, чтобы при работе процедуры удаления (4.64) она выполняла каждую из четырех подпрограмм балансировки по кра> ней мере один раз. Какова последовательность с минимальной 0 ной ?

4.22. Какова средняя длина пути в дереве Фибоначчи 7 п?

Имеются ли какие-либо простые соотношения между последоватв ностями узлов, получаемыми при этих порядках обхода и теми, котп рые дают три порядка, определенные выше в тексте? о-

1.14. Определите структуру данных для представления -арных деревьев Затем напишите процедуру, которая обходит п-арное дерево и f- -

3 Напишите программу, которая формирует дерево, близкое к опгн-* мальному в соответствии с алгоритмом, основанным на выборе центроида в качестве корня (4.78).

124. Предположим, что ключи 1, 2, 3 ... вставляются в пустое Б-дерево порядка 2 (программа 4.7). Какие ~;лючп вызывают расщепление страниц? Какие ключи вызывают увеличерие высоты дерева?

Если ключи удаляются в гом же порядке, то какие ключи вызы-

flL вают слияние (и освобождение) страниц и какие ключи вызывают уменьшение высоты? Ответьте на этот вопрос для случаев (а) схемы

Р-удаяення, использующей балансировку (как в программе 4.7), и (Ь) схемы без балансировки (при недостаче берется один элемент с со-

В седней страницы).

Щ5. Напишите программу поиска, включения и удаления ключей в бинарном Б-дереве. Используйте определение типа узла (4.84). Схема включения показана на рис. 4.51.

46. Найдите последовательность вставляемых ключей, которая, начиная

1С пустого симметричного бинарного Б-дерева, заставляет процедуру t (4.87) выполнить все четыре действия балансировки (LL, RR, LR, RL) [ по крайней мере один раз. Какова самая короткая последовательность? 7. Напишите процедуру удаления элементов в симметричном бинарном Б-дереве. Затем найдите дерево и короткую последовательность удалений, вызывающую появление всех четырех ситуаций балансировки хотя бы по одному разу.

4.28. Сравните работу алгоритма включения и удаления для бинарных деревьев, АВЛ-сбалансированных деревьев и для симметричных бинарных Б-деревьев на вычислительной машине. В частности, исследуйте влияние упаковки данных, т. е. экономного представления данных с

использованием только двух разрядов для хранения информацпи о сбалансированности каждого узла.

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

4.30. Если количество информации, связанной с каждым ключом, относительно велико (по сравнению с самим ключом), эту информацию не

рекомендуется помещать в рассеянную таблицу. Объясните почему и Щ предлолгйте схему для представления такого множества данных.

31. Рассмотрите предложения о решении проблемы скопления с помощью деревьев переполнения вместо списков переполнения, т. е. организа-

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

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

4.33. Основной недостаток метода расстановки состоит в том, что размер таблицы должен быть фиксированным, тогда как число элементов не-fc известно. Предположим, что ваша вычислительная система содержит Ш механизм динамического распределения памяти, который позволяет в любой момент выделять память. Следовательно, когда рассеянная

литература

4.1. Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации. - Доклады АН СССР, 146, 1962, с. 263-266.

АЛ, BAYER-Jt,-McCREXGHX-E, Organ.iz.atinn апН Maintenance of Laree Ordered Indexes. - Лс/о Informatica, 1, No. 3, 1972, 173-189.

4.3. BAYER R. Binary B-trees for Virtual Memory. - Proc. 1971 ACM SIGFIDET Workshop, San Diego, Nov. 1971, 219-235.

4.4. BAYER R. Symmetric Binary B-trees; Data Structure and Maintenance Algorithms. -i4cte Informatica, I, No. 4, 1972, 290-306.

4.5. ни Т. С. TUCKER A. C. - SIAM J. Applied Math. 21, No. 4, 1971 514-532.

4.6. KNUTH D. E. Optimum Binary Search Trees. - Acta Informatica, 1, No. 1, 1971, 1425.

4.7. MAURER W. D. An Improved Hash Code for Scatter Storage. - Comm. ACM, 11, 1968, No. 1, 35-38.

4.8. MORRIS R. Scatter Storage Techniques. - Comm. ACM, 11, No 1, 1968, 38-43.

4.9. PETERSON W. W. Addressing for Random-access Storage. - IBM J. Res. and Dev., 1, 1957, 130-146.

4.10. SCHAY G., SPRUTH W. Analysis of a File Addressing Method.-Comm. ACM, 5, No. 8, 1962, 459-462.

4.11. WALKER W. A.. GOTLIEB C. C. A Top-down Algorithm for Constructing Nearly Optimal Lexicographic Trees,. -Graph Theory and Computing, New York: Academic Press, 1972, pp. 303-323.

таблица Н заполнена (или почти заполнена), то формируется ббп шая таблица Н', и все ключи нз Н пересылаются в Н\ после ч^

ММу ром rt.

4.34. Очень часто ключи являются не целыми числами, а последовательно стями букв. Эти слова могут сильно различаться по длине и поэтому не могут удобно и экономно размещаться в полях фиксированного размера. Напишите программу, которая работает с рассеянной таблицей и ключами переменной длины.