Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 93
Текст из файла (страница 93)
увеличенной на единицу глубиной узла на дереве Т, в котором находится искомый ключ. Тоща математиче- заданная последовательность К = ()ст, )сз,..., к ), состоящая из и различных ключей, которые расположены в отсортированном порядке (так что кт < )сз < < )е„). Из этих ключей нужно составить бинарное дерево поиска Для каждого ключа Ц задана вероятность р; поиска этого ключа.
Кроме того, может выполняться поиск значений, отсутствующих в последовательности К, поэтому следует предусмотреть н+ 1 фиктивных ключей до, в(1, Из,..., И„, представляющих этн значения. В частности, по представляет все значения, меньшие кы а в(„— все значения, превышающие /с„.
Фиктивный ключ 4 (т = 1,2,..., и — 1) представляет все значения, которые находятся межщ йе и йв+ы Для каждого фиктивного ключа 4 задана соответствующая ей вероятность до На рис. 15.9 показаны два бинарных дерева поиска для множества, состоящего из и = б ключей. Каждый ключ Ц представлен внутренним узлом, а каждый фиктивный ключ 4 является листом. Поиск может быть либо успешным (найден какой-то ключ йт), либо неудачным (возвращается какой-то фиктивный ключ 4), поэтому справедливо соотношение Геаеа!5. динамическое нр«грие«мироеание 433 сюе ожидание стоимости поиска в дереве Т равно Е [стоимость поиска в Т) = ~~ («(ерСЬт(«с,) + 1) р, +~ ~(«(орет(4) + 1) д« «=1 «=о н п = 1+~~««(ереЬт(«с«) р«+~~««(ертЬт(«(«) «7«, (15.11) «=1 «=О где величина «(ерСЬт обозначает глубину узла в дереве Т.
Последнее равенство следует из уравнения (15.10). Используя приведенную на рис. 15.9 таблицу ве- роятностей, можно вычислить математическое ожидание стоимости поиска для бинарного дерева, изображенного в части (а) рисунка. Узел Глубина Вероятность Вклад Всего 2.80 Наша цель — построить для данного набора вероятностей бинарное дерево поиска, математическое ожидание стоимости поиска для которого будет минимазьным. Такое дерево называется оппсимальпым бинарным деревом поиска. На рнс.
15.9, (б) показано оптимальное бинарное дерево поиска для вероятностей, указанных в таблице в подписи к рисунку. Математическое ожидание стоимости поиска в этом дереве равно 2.75. Этот пример демонстрирует, что оптимальное бинарное дерево поиска — это не обязательно дерево минимальной высоты. Кроме того, в оптимальном дереве ключ, которому соответствует максимальная вероятность, не всегда находится в корне. В данном случае вероятность имеет самую большую величину для ключа lсз, хотя в корне оптимального бинарного дерева расположен ключ нз.
(Минимальная величина математического ожидания стоимости поиска для всевозможных бинарных деревьев поиска, в корне которых находится ключ )сз, равна 2.85.) Как и в задаче о перемножении цепочки матриц, последовательный перебор всех возможных деревьев в данном случае оказывается неэффективным. Чтобы сконструировать бинарное дерево поиска, можно обозначить ключами «сн йз,..., /сн узлы бинарного дерева с и узлами„а затем добавить листья для фиктивных ключей.
В задаче 12.4 было показано, что количество бинарных деревьев с и узлами равно П(4н/пз 2), так что количество бинарных деревьев, которые нужно проверять при полном переборе, растет экспоненциально с ростом и. Не )с« «сз кз ««4 «сз "о «1« «12 «(з «14 «15 0.15 0.10 0.05 0.10 0.20 0.05 0.10 0.05 0.05 0.05 О. 1О 0.30 0.10 0.15 0.20 0.60 0.15 0.30 0.20 0.20 0.20 0.40 434 Часть! У. Усовершенствованные мвтоды равраоотни и анатво удивительно, что эта задача будет решаться методом динамического программи- рования.
Этап 1. Структура оптимального бинарного дерева поиска Чтобы охарактеризовать оптимальную подструктуру оптимального бинарного дерева поиска, исследуем его поддеревья. Рассмотрим произвольное поддерево бинарного дерева поиска. Оно должно содержать ключи в непрерывном интервале Ц,..., й, для некоторых 1 < 1 < з < п. Кроме того, поддерево, содержащее ключи й;,..., й., должно также содержать в качестве листьев фиктивные ключи д, „...,~,. Теперь можно сформулировать оптимальную подструктуру: если в состав оптимального бинарного дерева поиска Т входит поддерево Т', содержащее ключи )с;,..., /ссь это поддерево также должно быть оптимальным для подзадачи с ключамн йс,...,)с. и фиктивными ключами с(с ы..., с( .
Для доказательства этого утверждения применяется обычный метод вырезания н вставки. Если бы существовало поддерево Т", математическое ожидание поиска в котором ниже, чем математическое ожидание поиска в поддереве Т', то из дерева Т можно было бы вырезать поддерево Т' и подставить вместо него поддерево Т". В результате получилось бы дерево, математическое ожидание времени поиска в котором оказалось бы меньше, что противоречит утверждению об оптимальности дерева Т. Покажем с помощью описанной выше оптимальной подструктуры, что оптимальное решение задачи можно воссоздать из оптимальных решений подзадач. Если имеется поддерево, содержащее ключи Й„..., йо, то один из этих ключей, скажем, к„(г < г < з) будет корнем этого оптимального поддерева.
Поддерево, которое находится слева от корня lс„, будет содержать ключи Ц,...,)с„1 (и фиктивные ключи сс, ы,,.,с(„з), а правое поддерево — ключи )с,.вы...,)с, (и фиктивные ключи с1„..., И ). Как только будут проверены все ключи й„(где 1 < т < 1'), которые являются кандидатами на роль корня, и найдены оптимальные бинарные деревья поиска, содержащие элементы lс„..., й„з и й„.вы..., йс, мы гарантированно построим оптимальное бинарное дерево поиска.
Стоит сделать одно замечание по поводу "пустых" поддеревьев. Предположим, что в поддереве с ключами кы...,)с в качестве корня выбран ключ Ры Согласно приведенным выше рассуждениям, поддерево, которое находится слева от корня йо содержит ключи Iс,,..., й; и Естественно интерпретировать эту последовательность как такую, в которой не содержится ни одного ключа. Однако следует иметь в виду, что поддеревья содержат, помимо реальных, и фиктивные ключи. Примем соглашение, согласно которому поддерево, состоящее из ключей Ц,...,)с» и не содержит обычных ключей, но содержит один фиктивный ключ с(, и Аналогично, если в качестве корня выбран ключ йо, то правое поддерево не содержит обычных ключей, но содержит один фиктивный ключ с(,.
Этап 2. Рекурсивное решение Теперь все готово для рекурсивного определения оптимального решения. В качестве подзадачи выберем задачу поиска оптимального бинарного дерева поиска, содержащего ключики...,Й,, где( > 1, з < пи) > 1 — 1(если 1 = г — 1,тофакти- Геава 1Т. Дииаиичесиое ирограимироваиие 43Т ческих ключей не существует, имеется только фиктивный ключ е(е з). Определим величину е[г, у] как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами Ц,..., Ус,. В конечном итоге нужно вычислить величину е[1, и]. Если у = 1 — 1, то все просто.
В этом случае имеется всего один фиктивный ключ дз и и математическое ожидание стоимости поиска равно е[г, 1 — 1] = рл у. Если Т > в, то среди ключей Ц,..., ЕТ нужно выбрать корень Уст, а затем из ключей Ц,...,Е„ у составить левое оптимальное бинарное дерево поиска, а из ключей Уе„иу, .,Уст — правое оптимальное бинарное дерево поиска. Что происходит с математическим ожиданием стоимости поиска в поддереве, когда оно становится поддеревом какого-то узла? Глубина каждого узла в поддереве возрастает на единицу.
Согласно уравнению (15.11) математическое ожидание стоимости поиска в этом поддереве возрастает на величину суммы по всем вероятностям поддерева. Обозначим эту сумму вероятностей, вычисленную для поддерева с ключами ц,..., учу, как ш(з, у) = ~р + ~. а (15. 12) у=у у=ч — 1 Таким образом, если Уе„ вЂ” корень оптимального поддерева, содержащего ключи й,,..., уе,, то выполняется соотношение е[з',Я = р„+ (е[з',т — 1] + ш(з,т — 1)) + (е[т+ 1,Я + ш(т+ 1, у)) . Заметив, что ш(г, Т) = ш(1, т — 1) + р„+ ш(т + 1, у), перепишем е[г, Т] как е[1, у] = е~г', т — 1] + е[т + 1, у] + ш(г, у) .
(15.13) Рекурсивное соотношение (15.13) предполагает, что нам известно, какой узел Уе, используется в качестве корня. На эту роль выбирается ключ, который приводит к минимальному значению математического ожидания стоимости поиска. С учетом этого получаем окончательную рекурсивную формулу: ]' а-у, если у =1 — 1, гшп (е[1, т — Ц + е[т + 1, у] + ш(г, у)), если 1 < у . ейт йз Величины е[(,у] представляют собой математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через твое[1, у] (где 1 < 1 < у < п) индекс т узла Ус„который является корнем оптимального бинарного дерева поиска, содержшцего ключи Ц,..., /с .
Хотя вскоре мы узнаем, как вычисляются величины тооу[з, у], способ восстановления из этих величин оптимального бинарного дерева поиска отложим до упр. ! 5.5.1. 436 Часть!К усовершенствованные методы разработан н ананша Этап 3. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска На данном этапе можно заметить некоторое сходство между характеристиками задач об оптимальных бинарных деревьях поиска и о перемножении цепочки матриц. Во вспомогательных задачах обеих задач индексы элементов изменяются последовательно. Прямая рекурсивная реализация уравнения (15.14) может оказаться такой же неэффективной, как и прямая рекурсивная реализация алгоритма в задаче о перемножении цепочки матриц. Вместо этого будем сохранять значения е[1,7] в таблице с[1..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
