Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 87
Текст из файла (страница 87)
Кроме того, в исходном тексте могут встречаться слова, для которых перевод отсутствует. Таких слов вообще не должно быль в бинарном дереве поиска. Как организовать бинарное дерево поиска, чтобы свести к минимуму количество посещенных в процессе поиска узлов, если известно, с какой частотой встречаются слова? Необходимая нам конструкция известна как оптимальное быпарпое дерево поиске (ор11ша! Ь(пату зеагсЬ пее). Приведем формальное описание задачи.
Имеется заданная последовательность К = (/сы йз,..., 1с„), состоящая из и различных ключей, которые расположены в отсортированном порядке (так что lсз < Йз < « )с„). Из этих ключей нужно составить бинарное дерево поиска. Для каждого ключа 1с, задана вероятность р; поиска этого ключа. Кроме того, может выполняться поиск значений, отсутствующих в последовательности К, поэтому следует предусмотреть и+ 1 фиктивных ключей (Но, Ны..., Н„), представляющих эти значения. В частности, 4> представляет все значения, меньшие йы а е'„— все значения, превышающие 1с„.
Фиктивный ключ 4 (г = 1, 2,..., и- 1) представляет все значения, которые находятся между Ц и Ц+н Для каждого фиктивного ключа 4 задана соответствующая ей вероятность дь На рис. 15.7 показаны два бинарных дерева поиска для множества, состоящего из п = 5 ключей.
Каждый ключ к, представлен внутренним узлом, а каждый фиктивный ключ 4 является листом. Поиск может быть либо успешным (найден какой-то ключ Ц), либо неудачным (возвращается какой-то фиктивный ключ 4), поэтому справедливо соотношение и п (15.15) Вероятности, соответствующие внутренним узлам р; и листьям дн приведены в табл. 15.1. Поскольку вероятность поиска каждого обычного и фиктивного ключа считается известной, можно определить математическое ожидание стоимости поиска Глава 15. Динамическое программирование 427 ,М. ,Г М ~ ф« ф 'А«« ~.','« 'я ) м,~ а) б« Рис. 15.7.
Два бинарных дерева поиска для множества из 5 злемевтов Таблица 15.1. Вероятности поиска ключей в узлах бинарного дерева 1 2 3 4 5 0 0,05 0,10 0,20 0,05 0,05 О, 10 0,15 0,10 0,10 0,05 0,05 по заданному бинарному дереву поиска Т. Предположим, что фактическая стои- мость поиска определяется количеством проверенных узлов, т.е. увеличенной на единицу глубиной узла на дереве Т, в котором находится искомый ключ. Тогда математическое ожидание стоимости поиска в дереве Т равно Е 1Стоимость поиска в Т~) = ~ (г1ерМТ (к;) + 1) р«+ «=1 + ,'« . (~ерй«т (А) + 1) % «=О п =1+~~, '(ер11тй) р*+ «ьц +~' ~1ергЛт(А) % «=О (15.16) где величина Нерглт () обозначает глубину узла в дереве Т. Последнее равенство следует из уравнения (15.15).
В табл. 15.2 вычисляется математическое ожидание стоимости поиска для бинарного дерева, изображенного на рис. 15.7а. Наша цель — построить для данного набора вероятностей бинарное дерево поиска, математическое ожидание стоимости поиска для которого будет Часть 1Ч. Усовершенствованные методы разработки и анализа 428 Таблица 15.2. Вычисление математического ожидания стоимости поиска Глубина Вероятность Вклад Узел 2,80 Всего минимальным. Такое дерево называется оптимальным бинарным деревом поиска.
На рис. 15.76 показано оптимальное бинарное дерево поиска для вероятностей, заданных в табл. 15,1. Математическое ожидание поиска в этом дереве равно 2.75. Этот пример демонстрирует, что оптимальное бинарное дерево поиска — это не обязательно дерево минимальной высоты. Кроме того, в оптимальном дереве ключ, которому соответствует максимальная вероятность, не всегда находится в корне.
В данном случае вероятность имеет самую большую величину для ключа й5, хотя в корне оптимального бинарного дерева расположен ключ йг. (Минимальная величина математического ожидания для всевозможных бинарных деревьев поиска, в корне которых находится ключ 145, равна 2.85.) Как и в задаче о перемножении цепочки матриц, последовательный перебор всех возможных деревьев в данном случае оказывается неэффективным. Чтобы сконструировать бинарное дерево поиска, можно обозначить ключами йы йг,..., 1с„узлы бинарного дерева с г4 узлами„а затем добавить листья для фиктивных ключей. В задаче 12-4 было показано, что количество бинарных деревьев с п узлами равно й (4"/пзбг), так что количество бинарных деревьев, которые надо проверять при полном переборе, растет экспоненциально с ростом и.
Не удивительно, что эта задача будет решаться методом динамического программирования. й1 йг Йз К4 К5 4) Из пг пз ~14 о5 0,15 0,10 0,05 0,10 0,20 0,05 0,10 0,05 0,05 0,05 0,10 0,30 0,10 0,15 0,20 0,60 0,15 0,30 0,20 0,20 0,20 0,40 Глава 15. Динамическое программирование 429 Этап 1: структура оптимального бинарного дерева поиска Чтобы охарактеризовать оптимальную подструктуру оптимального бинарного дерева поиска, исследуем его поддеревья.
Рассмотрим произвольное поддерево бинарного дерева поиска. Оно должно содержать ключи, которые составляют непрерывный интервал Ц,...,/с для некоторых 1 < ю' < 1 < п. Кроме того, такое поддерево должно также содержать в качестве листьев фиктивные ключи г/ -~ ~ г//. Теперь можно сформулировать оптимальную подструктуру: если в состав оптимального бинарного дерева поиска Т входит поддерево Т', содержащее ключи /г;,..., /сс/, то это поддерево тоже должно быть оптимальным для вспомогательной подзадачи с ключами й,,..., й и фиктивными ключами г/; м...,г/ . Для доказательства этого утверждения применяется обычный метод "вырезания и вставки".
Если бы существовало поддерево Т", математическое ожидание поиска в котором ниже, чем математическое ожидание поиска в поддереве Т', то из дерева Т можно было бы вырезать поддерево Т' и подставить вместо него поддерево Т". В результате получилось бы дерево, математическое ожидание времени поиска в котором оказалось бы меньше, что противоречит оптимальности дерева Т. Покажем с помощью описанной выше оптимальной подструктуры, что оптимальное решение задачи можно воссоздать из оптимальных решений вспомогательных задач.
Если имеется подлерево, содержащее ключи /т,..., й,, то один из этих ключей, скажем, й, (з < г < 1) будет корнем этого оптимального поддерева. Поддерево, которое находится слева от корня й„, будет содержать ключи /г„...,й„~ (и фиктивные ключи г/; ы...Н, ~), а правое поддерево— ключи й,+ы...,/с/ (и фиктивные ключи г/„...,г/ ). Как только будут проверены все ключи Й„(где г < г < 1), которые являются кандидатами на роль корня, и найдем оптимальные бинарные деревья поиска, содержащие элементы Ц,..., й„~ и /г„+ы..., к/, мы гарантированно построим оптимальное бинарное дерево поиска.
Стоит сделать одно замечание по поводу "пустых" поддеревьев. Предположим, что в поддереве с ключами Ц,...,/с в качестве корня выбран ключ /с,. Согласно приведенным выше рассуждениям, поддерево, которое находится слева от корня /со содержит ключи Ц,..., Ц и Естественно интерпретировать эту последовательность как такую, в которой не содержится ни одного ключа.
Однако следует иметь в виду, что поддеревья содержат помимо реальных и фиктивные ключи. Примем соглашение, согласно которому поддерево, состоящее из ключей /с;,...,/г; ы не содержит обычных ключей, но содержит один фиктивный ключ г/; н Аналогично, если в качестве корня выбран ключ /с/, то правое поддерево не содержит обычных ключей, но содержит один фиктивный ключ Н . Часть )У. Усовершенствованные методы разработки н анализа 430 Этап 2: рекурсивное решение ю(г, т') = ~) р!+ ~~) дь (15.
17) [=с-1 Таким образом, если к„— корень оптимального поддерева, содержащею ключи Й,,..., ЙЗ, то выполняется соотношение е [г, Я = рт + (е [г, т — Ц + ю (г, т — 1) ) + (е [т + 1, Я + и (т + 1, у) ) . Заметив, что и (г, 7) = ю (г, т — 1) + р„+ ю(т + 1, у), выражение для величины е [г, 7] можно переписать так: е [г, 7'] = е [г, т — Ц + е [т + 1, Я + ю (г, у) . (15.18) Рекурсивное соотношение (15.18) предполагает, что нам известно, какой узел /с„используется в качестве корня. На эту роль выбирается ключ, который приводит к минимальному значению математического ожидания стоимости поиска. С учетом этого получаем окончательную рекурсивную формулу: е[с,7'] = 91-! при у' =1 — 1, ш!и (е [с, т — Ц + е [т + 1, у] + и (г, 7)) при 1 < Я (15.19) с<тьэ Теперь все готово для рекурсивного определения оптимального решения.
В качестве вспомогательной задачи выберем задачу поиска оптимального бинарного дерева поиска„содержащего ключи Ц,...,/сз, где 1 > 1, у < и и у > с' — 1 (если у = 1 — 1, то фактических ключей не существует, имеется только фиктивный ключ с(с 1). Определим величину е [г, Я как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами Ц,..., !с . В конечном итоге нужно вычислить величину е [1, и].
Если 7' = с' — 1, то все просто. В этом случае имеется всего один фиктивный ключ 4 и и математическое ожидание стоимости поиска равно е [т, 1 — Ц = йя ь Если 7' > 1, то среди ключей /с,,..., /су нужно выбрать корень !с„, а потом нз ключей !с;,..., /с„з составить левое оптимальное бинарное дерево поиска, а из ключей к,+ы..., !су — правое оптимальное бинарное дерево поиска. Что происходит с математическим ожиданием стоимости поиска в поддереве, когда оно становится поддеревом какого-то узла? Глубина каждого узла в поддереве возрастает на единицу.
Согласно уравнению (! 5.16), математическое ожидание стоимости поиска в этом поддереве возрастает на величину суммы по всем вероятностям поддерева. Обозначим эту сумму вероятностей, вычисленную для поддерева с ключами й;,...,Й,, так: Глава 15. Динамическое программирование 431 Величины е [г, з) — это математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через гоо1 [г', з] (где 1 < 1 < < з < и) индекс т узла lс„, который является корнем оптимального бинарного дерева поиска, содержащего ключи Ц,..., /с .
Скоро мы узнаем, как вычисляются величины гоо1 [г, з], а способ восстановления из этих величин оптимального бинарного дерева поиска оставим до того момента, когда придет время выполнить упражнение 15.5-1. Этап 3: вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска На данном этапе некоторые читатели, возможно, заметили некоторое сходство между характеристиками задач об оптимальных бинарных деревьях поиска и о перемножении цепочки матриц. Во вспомогательных задачах обеих задач индексы элементов изменяются последовательно. Прямая рекурсивная реализация уравнения (15.19) может оказаться такой же неэффективной, как и прямая рекурсивная реализация алгоритма в задаче о перемножении цепочки матриц. Вместо этого будем сохранять значения е [с, з] в таблице е [1..и+ 1,0..п].
Первый индекс должен пробегать не и, а п + 1 значений. Это объясняется тем, что для получения поддерева, в который входит только фиктивный ключ 4,„понадобится вычислить и сохранить значение е [п+ 1, и]. Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ с(о, нужно вычислить и сохранить значение е [1, О].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
