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

Мы завершим этот раздел доказательством того, что рассмотренный алгоритм дает дерево двоичного поиска, минимизирующее EQ= =2pi/j. Предположим, что pt упорядочены, т. е. piPzK- -Рт-Алгоритм объединяет pi и ра в одной вершине и затем решает редуцированную задачу с m-l объектами. Когда решена редуцированная задача, вершина на рис. 5.2.9, а в дереве, соответствующем решению редуцированной задачи, заменяется на поддерево, показанное на рис. 5.2.9, б. Пусть Т„ - дерево, минимизирующее EQ, aw - внутренняя вершина, т. е. максимально удаленная от корня. Если pi и ра не являются вероятностями, приписанными преемникам вершины v, то можно эти значения поменять местами со значениями вероятностей действительных преемников v, не увеличивая значения EQ. Это новое дерево минимизирует EQ и содержит поддерево с рис. 5.2.9, б.

Пусть Тт-1 будет дерево Т, в котором поддерево с рис. 5.2.9, б заменено вершиной с рис. 5.2.9, а. Если мы сможем показать, что Т,п-1 оптимально для задачи Р„, тогда и только тогда, когда 7, оптимально для Р„, то простая индукция докажет правильность алгоритма. Мы покажем явно, что если Т оптимально для Р„, то Тт-1 будет оптимально для Предположим, что T-i не

оптимально для а Т. оптимально. Тогда EQ (T;; )<

<EQ(T;„ i). По условию задачи дерево Т; должно иметь

конечную вершину такого вида, как на рис. 5.2.9, а. Заменим эту вершину поддеревом с рис. 5.2.9, б и назовем это новое дерево Т. Тогда

EQ (Г) = EQ (Т; 0 -f Pi -f Pa < EQ (Г;. ,) Ч- Pi -f Pa = EQ (TJ, что противоречит утверждению, что Т оптимально для Р.

Упражнения 5.2

5.2.1. Постройте блок-схемы алгоритмов BSEARCH и BTSI.

5.2.2. Постройте дерево двоичного поиска для следующего списка ключей:

6 17 21 35 46 51 59 66 78 83

5.2.3. Последовательный поиск (разработка). Разработайте простой алгоритм последовательного поиска (см. второй абзац этого раздела).

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

5-2.5. Воспользуйтесь алгоритмом BTSI для того, чтобы вставить населенный пункт caggsville (население 350) в дерево на рис. 5.2.5.

5-2.6. Проверьте, что a=l+(d/dz)[{Sk(2z)-l)z] при 2=1.

(A-lo)g

Рис. 5.2.8. Оптимальное дерево решений, получаемое последовательным объединением двух множеств с наименьшими вероятностями.

Рис. 5.2.9. Объединение двух наименьших вероятностей Рх и Р.

L5.2.7. Алгоритм BTSI (реализация, проверка) Реализуйте и проверьте алгоритм BTSI.

L5.2.8. Алгоритм BSEARCH (реализация, проверка). Реализуйте и проверьте алгоритм BSEARCH. Экспериментально убедитесь в том, что его сложность логарифмическая.

**5.2.9. Алгоритм BSEARCH (анализ). Обобщите анализ математического ожидания трудоемкости, приведенный в данном разделе, на случай, когда дерево поиска неполно.

*5.2.10. Дайте явную пошаговую формулировку алгоритма удаления вершин- см. рис. 5.2.5.

5.2.11. Воспользуйтесь процедурой Хафмэна - Циммермана, чтобы построить оптимальное дерево поиска для задачи с семью объектами и вероятностями выбора: pi=0.05, Р2=0.10, рз=0.10, р4=0.15, р5=0.16, Рб=0.20, /?,=0.24.

•*L5.2.I2. Вероятностный поиск (полное построение). Постройте следующую модификацию алгоритма двоичного поиска: вместо деления пополам интервала на каждом этапе поиска обращайтесь к случайно выбираемым элементам с равными вероятностями. Сравните трудоемкость этого алгоритма с трудоемкостью алгоритма двоичного поиска.

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

**5.2.14. Дайте явную формулировку алгоритма Хафмэна - Циммермана.

*L5.2.15. Задача выбора (полное построение). Постройте алгоритм решения задачи выбора: Для произвольного набора из п входных чисел найти k-e по величине число. Входные числа предварительно не упорядочены. Предположите, что k - фиксированное целое число и что 1<:А<:п.

5.2.16. Длины путей в двоичном дереве с корнем (анализ). Определите длину внешнего пути EPL двоичного дерева с корнем как сумму по всем конечным вершинам длин единственных путей от корня к каждой конечной вершине. Длина внутреннего пути IPL определяется аналогично через сумму по всем внутренним вершинам. Покажите, что если в дереве N внутренних вершин, то EPL=IPL+2W.

**L5.2.I7. Поиск в лабиринте (разработка, реализация). Пусть М - матрица 15x15, элементами которой являются буквы «О» (для «открьгго») и «3» (для «закрыто»). Кагкдый элемент выбирается случайно с вероятностями Р(0)=2/3 и Р(3)=1/3. Наша цель состоит в отыскании пути, составленного из горизонтальных и вертикальных отрезков, соединяющих соседние элементы, который проходит от позиции (1, 1) до позиции (15, 15). Запрещено проходить через элементы 3. Все элементы нута должны быть буквами О.

5.3. Арифметические и логические выражения

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

Задача чтения произвольной последовательности S=S(1), S(2), . . ., S(N), состоящей из символов, и принятия решения о том, что