Главная Промышленная автоматика.

щий символ /, мы не сможем вставить всю последовательность ticdef, начиная процесс от корня. Также отметим, что имея последовательность abcde, мокно создать узлы для последовательностей bcde, cde, de и е, которые в итоге будут нам необходимы. Измените структуру данных нагрркенного дерева для под-держси таких указателей и модифицируйте алгоритм вставки в нагрркенное дерево с учетом особенностей этой структуры данных.

5.7. Нарисуйте 2-3 дерево, которое получится в результате вставки в пустое множество (представленное как 2-3 дерево) элементов 5, 2, 7, О, 3, 4, 6, 1, 8, 9.

5.8. Покажите результат удаления элемента 3 из 2-3 дерева, полученного в упражнении 5.7.

5.9. Покажите последовательные значения всех множеств S, которые получаются в процессе выполнения алгоритма наховдения НОП из листинга 5.15 при сравнении последовательностей abacabada и bdbacbad.

5.10. Предположим, что мы используем 2-3 дерево для реализации операторов

MERGE и SPLIT из раздела 5.6:

а) покажите результат разбиения дерева из упражнения 5.7 по элементу 6;

б) выполните слияние дерева из упражнения 5.7 с деревом, состоящим из листьев элементов 10 и 11.

5.11. Некоторые структуры, описанные в этой главе, легко модифицировать для реализации АТД MAPPING (Отображение). Напишите процедуры MAKENULL, ASSIGN и COMPUTE для их выполнения над АТД MAPPING при использовании следующих структур данных:

а) деревья двоичного поиска. В области определения отображения упорядочьте элементы посредством отношения порядка "<";

б) 2-3 деревья. Во внутренних узлах поместите только поле ключей элементов области определения.

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

5.13. Используйте пример 5.12 для создания нерекурсивной версии процедуры DELETEMIN.

5.14. Напишите процедуры ASSIGN, VALUEOF, MAKENULL и GETNEW для уздов нагрркенного дерева, представленных в виде списков.

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

*5.16. Если элементы множества упорядочены посредством отношения "<", тогда во внутренних узлах 2-3 дерева можно хранить один или два элемента (не обязательно ключи), и в этом случае не обязательно, чтобы элементы хранились в листьях дерева. Напишите процедуры INSERT и DELETE для 2-3 дерева этого типа.

5.17. Другая модификация ,2-3 деревьев предполагает хранение во внутренних узлах дерева только ключей ky и k, но не обязательно именно минимальных ключей второго и третьего поддеревьев. Требуется только, чтобы все ключи к третьего поддерева удовлетворяли неравенству к > Аг» все ключи к второго поддерева - неравенствам < к < к2, а для всех ключей к первого поддерева выполнялось : < fy.

а) как в рамках этих соглашений упростить реализацию оператора DELETE?

б) какие из операторов словарей и отображений при использовании таких 2-3 деревьев будут выполняться более эффективно, а какие менее?



*5.18. Еще одной структурой данных, которая поддерживает словари с оператором MIN, являются АВЛ-деревьл (названные так в честь авторов Г.М. Адельсона-Вельского и Е.М. Ландиса), или деревья, сбалансированные по высоте. Эти деревья являются деревьями двоичного поиска, у которых для кавдого узла высоты его правого и левого поддеревьев отличаются не более чем на единицу. Напишите процедуры реализации операторов INSERT и DELETE при использовании АВЛ-деревьев.

5.19. Напишите на языке Pascal программу для процедуры insertl из листинга 5.12.

*5.20. Конечный автомат состоит из множества состояний, которые мы будем обозначать целыми числами от 1 до п, таблицы переход[состояние, вход], которая для каждого состояния и для каждого символа вход определяет следующее состояние. Предполоким, что входом всегда является или О или 1. Далее, определенные состояния назначаются допускающими состояниями. Для наших целей цредполоким, что только состояния, выражающиеся четными числами, являются допускающими. Два состояния называются эквивалентньши, если являются одним и тем же состоянием, или (1) они являются допускающими или оба недопускающими; (2) вход О они преобразуют в эквивалентные состояния и (3) вход 1 они таюке преобразуют в эквивалентные состояния. Очевидно, что эквивалентные состояния "работают" одинаково на всех последовательностях входов, т.е. на основании конкретных входов оба или достигнут множества допускающих состояний, или не достигнут этого множества. Напишите программу, использующую операторы АТД MFSET, которая бы вычисляла множества эквивалентных состояний для данного конечного автомата.

**5.21. Для реализации АТД MFSET посредством деревьев покажите, что

а) если используется сжатие путей и разрешается сливать только большие деревья в меньшие, то для выполнения п операций слияния требуется время порядка П(п logn);

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

5.22. Выберите структуру данных и напишите программу вычисления множеств PLACES (определены в разделе 5.6), которая выполнялась бы за среднее время порядка 0(п) для строк длиной и.

*5.23. Измените процедуру НОП из листинга 5.15 так, чтобы она действительно вычисляла НОП.

*5.24. Напишите программу SPLIT для работы с 2-3 деревьями.

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

Библиографические примечания

Нагрркенные деревья (trie) впервые предложены в работе [38]. В [6] введены В-деревья (с которыми мы познакомимся в главе И) как обобщения 2-3 деревьев. Впервые использовали деревья 2-3 для вставки и удаления элементов и для слияния и разбиения множеств Дж. Хопкрофт (J. Е. Hopcroft) в 1970 г. (не опубликовано), а для оптимизации кодов - Дк. Ульман (J. D. Ullman) [111].

Структуры деревьев из раздела 5.5, использующие сжатие путей и слияние меньших деревьев в большие, впервые применили М. Мак-Илрой (М. D. МсИгоу) и Р. Моррис (R. Morris) для построения остовных деревьев минимальной стоимости. Реа-



лизация АТД MFSET посредством деревьев проанализирована в работах [31] и [53]. Упражнение 5.21,6 взято из статьи [108].

Решение задачи НОП из раздела 5.6 приведено в [55]. Эффективная структура данных для операторов FIND, SPLIT и суясенного оператора MERGE (когда все элементы в одном множестве меньше по величине, чем в другом) приведена в статье [113].

Упражнение 5.6 основано на эффективном алгоритме сравнения шаблонов, разработанном в [116]. Вариант 2-3 деревьев из упраяснения 5.16 подробно рассмотрен в монографии [126]. Структура АВЛ-деревьев для упраяснения 5.18 взята из работы [1].





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 [56] 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0019