AOP_Tom1 (1021736), страница 114
Текст из файла (страница 114)
Расслютрим множество х+уч-х~+ ..+х +ивершинг„вл,1, (1 <л<х+у,1<1<и,1<к<я).для которых дуги проходят от взл к Г„для всех л и (с. Согласно результату упр. 27 существует (х+ у)(х+ у+ хл+ +х„)" ' таких способов проведения дуг среди вершин гл,...,1„, что полученный в результате ориентированный граф не будет содержать ориентированных циклов. Используйте этот результат для доказательства предложенного Гурвицем обобщения биномиальной теорелгы. ) х(х+слх~+ +е„х„) 'ч + " ~у(у+(1 — е~)хл ь +(1 — с )х ) = (х+у)(х+у+л,+ +хь)" где суллма берется по всем 2" вариантам наборов ец..., е, состоящих из нулей и единиц.
31. [МУ4) Решите задачу из упр. 5 для упорядоченных деревьев, т. е. постройте производншую функцию для определения количества непомеченных упорядоченных деревьев с и концевыми узлами и без узлов со степенью 1. 32. [Му7[ (Задача А. Эрдейи (А. Егбе!у1) и А. М, Х. Этерингтона (1.
М. Н, ЕлЬеппблоп);. см. ЕпбпЬнга1~ Маей. 1лощез 32 (1940), 7 — 12). Сколько существует упорядоченных и непомеченных деревьев с ие уз~вин со степенью О, с и~ узлами со степенью 1, ..., с и узлами со степенью гл и без узлов со степенями выше т? (Решение этой задачи можно представить в явном виде с помощью факторивлов и тем самым существенно обобщить результат упр.
11.) ь ЗЗ. [Муу) В этом разделе в явном виде дано решение уравнения ш = у~с" + . +у,е*" которое основано на формулах перечислении для некоторых ориентированных лесов. Аналогично покажите, что формула перечисления нз упр. 32 позволяет получить решение ш уравнения ш — х нб~ +х ш л +...+хш явно в виде степенного ряда хц ..,, х . (Здесь ем..., е„— фиксированные неотрицательные целые числа, среди которых по крайней мере одно равно нулю.) 2.3.4.5. Длина пути.
Понятие "длина пути" дерева имеет большое значение для анализа алгоритмов, так как эта величина часто непосредственно связана со временем их выполнения. В таком смысле наибольший интерес вызывают бинарные деревья, поскольку они максимально близко отражают представление данных в компьютере. Ниже в настоящем разделе мы будем рассматривать схемы бинарного дерева в расширенном виде: добавим к диаграмме дерева специальные узлы в местах, где в исходном дереве присутствуют пустые поддеревья, таким образом, что дерево примет вид Полученное дерево называется расширенным бииарнъьм деревом (ех$епдед 61пагд атее).
После добавления квадратных узлов получим более удобную для работы структуру, которая будет довольно часто использоваться в последующих главах. Ясно, что каждый круглый узел имеет двух детей, а каждый квадратный — ии одного (ср. с 2.3-20). Если в дереве имеется и круглых и г квадратных узлов, то в нем имеется также п + г — 1 ребер (поскольку эта диаграмма — свободное дерево). Подсчитывая количество ребер другим способом, т. е. по количеству детей, получим 2и ребер.
Отсюда следует, что (2) Иначе говоря, количество добавленных "внешних" узлов на единицу больше исходного количества "внутренних" узлов. (Другое доказательство приводится в упр. 2.3.1 — 14.) Формула (2) справедлива даже для п = О. Предположим, что бинарное дерево расширено именно таким образом. Тогда длина внешнего пдтпи дерева (ехйегпа! рагЛ (еидгЛ о1 йе 1гее), Е, определяется, как сумма длин путей от корня к каждому узлу, взятая по всем внешним (кввдратным) узлам. Длина внутреннего пугин дерева ((пгегпа! ра1Л 1епд1Л), 1, определяется так же, но суммирование длин путей выполняется по внутренним (круглым) узлам.
Для дерева (1) длина внешнего пути равна Е = 3+ 3+ 2+ 3+ 4+ 4+ 3+ 3 = 25, а длина внутреннего пути равна 1 = 2+ 1+ Оь 2+ 3+ 1+2 = 11. Эти две величины, очевидно, связаны формулой (3) Е=1+2п, где и†количество внутренних узлов. Для доказательства соотношения (3) удалим внутренний узел Ъ', который находится на расстоянии Л от корня, где оба ребенка вершины 1' — внешние узлы.
Величина Е при этом уменьшается на 2(Л+ 1), так как удаляются дети узла Ъ', и в то же время увеличивается на Л, так как узел 1 становится внешним. В целом, изменение величины Е равно — Л вЂ” 2, а изменение величины 1 равно — Л. Далее справедливость формулы (3) доказывается по индукции. Нетрудно видеть, что внутренняя длина пути (а значит, и внешняя длина пути) достигает наибольшего значения, когда дерево становится вырожденным, т. е. имеет линейную структуру. В этом случае длина внутреннего пути составляет п — и г (п — 1) + (п — 2) + + 1+ О = 2 Можно показать, что "средняя" длина пути для всех бинарных деревьев прямо пропорциональна пь/й (см. упр.
5). Расслготрим теперь задачу построения бинарного дерева с и узлами, которое обладает минимальной длиной пути. Деревья такого типа имеют большое практическое значение, так как с их помощью можно сократить до минимума время выполнения различных алгоритмов. Ясно, что только один узел (корень) может находиться на нулевом расстоянии от корня. Далее, не более двух узлов может находиться на расстоянии 1 от корня, не более четырех узлов †- на расстоянии 2. и т. д.
Следовательно, внутренняя длина пути всегда яе меньше суммы первых и членов ряда О. 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4., 4, 4, 4, Эту сумму можно выразить формулой 2 ., (1бЦ, которая, как нам известно из результата упр. 1.2.4 — 42, равна (и + 1)п — 2~+ + 2. о = ()к(п + 1Ц (4) Оптимальное значение (4) равно и 1яи+ 0(п), так как д = 1к и+ 0(1). Ясно, что этот результат достигается, например, в дереве следующего типа (здесь представлена схема дерева для п = 12).
(5) Дерево типа (5) называется полным бинарпы.м деревом (сотр!е1с Ьспагу 1гее) с и внутренними узлами. В общем случае люжно перенумеровать внутренние узлы 1,2,,п. Эта нумерация удобна тем, что родителем узла и является узел (1с/2), а детьми узла и — узлы 2Й и 2к+ 1. Внешние (концевые) узлы нумеруются соответственно числами от и+ 1 до 2п+ 1 включительно Отсюда следует, что полное бинарное дерево можно очень просто представить в последовательных ячейках памяти, причем его структура будет неявно задана не связями, а самим порядком расположения узлов.
Полные бинарные деревья в явном илн неявном виде применяются в очень многих важных компьютерных алгоритмах, поэтому читателю следует уделить им особое внимание Рассматриваемые понятия можно обобщить для тернарных, кватериарных и других деревьев более высокого порядка. Определим 1;арное дерево (1-агу ггее) как множество узлов, которое либо пусто, либо состоит из узла и 1 упорядоченных и непересекающихся барных деревьев. (Это определение обобщает определение бинарного дерева из раздела 2.3.) Полное тернарпое дерево (сотпр1е1е 1егпагу 1гее) с 12 внутренними узлами имеет такой вид Нетрудно видеть, что описанное выше построение обобщается для любого ! > 2. В полном 1-арном дереве с внутренними узлами (1, 2,..., и) родителем узла й будет узел ((Й+ ! — 2)/!! = ((Й вЂ” 1)!!), а детьми узла !с — узлы !(й — ц+2, г(й — 1)+3, ..., ! +1.
Это дерево имеет минимальную внутреннюю длину пути среди всех 1-арных деревьев с и внутренними узлами. В упр. 8 приводится доказательство того, что его внутренняя длина пути равна Эти результаты имеют еще одно важное обобщение, если рассмотреть их с несколько другой точки зревия. Пусть даны т действительных чисел юы юг, ..., ю . Задача заключается в поиске расширенного бинарного дерева с т внешними узлами и такого соответствия между числами 1сы ..,, и1ю и узлами этого дерева, при котором сумма 1 юг! является минимальной, где ! — длина пути от корня, а сумма берется по всем внешним узлам. Например, если заданы числа 2, 3, 4, 11,. можно построить три таких расширенных бинарных дерева.
(8) Здесь "взвешенными" длинами пути 2 , 'ю,1, будут 34, 53 и 40 ссатветственно. (Как видно из данного примера, с помощью полностью сбалансированного дерева нельзя получить минимальное значение взвешенной длины пути для весов 2, 3, 4 и 11, хотя, как показано выше, это возможно в особом случае, с весами ю1 — — юг = . — — ю = 1.) В разных компьютерных алгоритмах понятие взвешенной длины пути может интерпретироваться по-разному. Например, с его помощью можно выполнять слияние упорядоченных последовательностей с длинами юы юг,..., ю (см.
главу 5). Одно из наиболее непосредственных приложений этого понятия заключается в том, что бинарное дерево рассматривается как некая программа поиска. Поиск начинается в корне с проверкой некоторого условия, затем в зависимости от его результата происходит переход к одной нз двух ветвей, где снова проверяется некоторое условие, и т. д. Например, если необходимо выполнить проверку истинности четырех раз- г з л и личных Условий, а веРоЯтности их истинности Равны соответственно го, го, тб и .
„, то дерево, которое минимизирует взвешенную длину пути, и будет представлять собой оптимальную программу поиска (орйта! геагсй ргоседиге). [Эти вероятности равны указанным в (8) весам, если умножить их на нормировочный множитель 20.) Следующий элегантныи алгоритм поиска дерева с минимальной взвешенной длиной пути был предложен Д. Хаффмэном [П. Ни%пап, Ргос. 1ВЕ 40 (1952), 1098 — 1101). Сначала нужно найти два наименьших веса и, например пч и шю После этого задача решается для гп — 1 весов нь + ю„вз,..., щ, причем в ее решении узел заменяется узлом (10) В качестве примера использования метода Хаффмэна найдем оптимальное дерево для весов 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. Для этого сначала объединим вершины 2+ 3 и найдем решение для 5,5,7,...,41, затем объединим 5+ 5 и т, д.
В общем, последовательность действий будет выглядеть так. 2 3 5 7 11 13 17 19 23 29 31 37 41 5 о 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 11 И 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 34 42 53 31 37 41 42 53 65 И 41 42 зЗ 65 78 95 95 7й 95 143 238 Следовательно, такому построению Хаффмэна будет соответствовать дерево (Числа в круглых узлах показывают связь между деревом и этапами приведенного выше вычисления; см. также упр. 9.) Нетрудно доказать с помощью метода индукции по гл, что этот способ действительно позволяет минимизировать взвешенную длину пути, Допустим, что даны веса ю~ < юз < юз < ° < ю, где гл > 2, и дерево, которое минимизирует взвешенную длину пути, (Такое дерево должно существовать, так как существует только конечное множество бинарных деревьев с т концевыми узлами.) Пусть ]г— внутренний узел, который находится иа максимальном расстоянии от корня.
Если веса юз и юз еще не приписаны детям узла 1г, то ими можно заменить величины, которые уже там находятся, не увеличивая взвешенную длину пути. Таким образом, существует дерево, которое минимизирует взвешенную длину пути и содержит поддерево (10). Теперь можно легко доказать, что взвешенная. длина пути подобного дерева будет минимальной тогда и только тогда, когда это дерево с поддеревом (10), замененным узлом (9), обладает минимальной длиной пути для весов ю~ + юз юз,...,ю,„. (см. упр. 9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
