из которого следует биномиаьная теорема Абеля, см. (16) в разделе 1.2.6. Ср. также с (30) из того же раздела.]

30. [М23} Пусть п,х,у, zi,. . 2„ -положительные целые числа. Рассмотрим множество X + у + zi + + z„ + п вершин п, Sjk, tj{l<i<x + y, l<j<n, 1<к< zj), для которых дуги проходят от Sjk к tj для всех j и к. Согласно результату упр. 27 существует

(х + у)(х +1/ + 21 Н-----\- Zn)"~ таких способов проведения дуг среди вершин <i,..., t„, что

полученный в результате ориентированный граф не будет содержать ориентированных циклов. Используйте этот результат для доказательства предложенного Гурвицем обобщения биномиальной теоремы.

ж(ж+£1г,+- .+enZ„Y+-+"-y{y+il-ti)zi + - + {1-еп)гпТ~~"~"~"

= {x + y){x + y+zi + --+zn)~\ где сумма берется по всем 2" вариантам наборов ei,... ,б„, состоящих из нулей и единиц.

31. [М24] Решите задачу из упр. 5 для упорядоченных деревьев, т. е. постройте производящую функцию Для определения количества непомеченных упорядоченных деревьев с п концевыми узлами и без узлов со степенью 1.

32. [М37] (Задача А. Эрдейи (А. Erdelyi) и А. М. X. Этерингтона (I. М. И. Ethering-ton); см. Edinburgh Math. Notes 32 (1940), 7-12). Сколько существует упорядоченных и непомеченных деревьев с по узлами со степенью О, с п] узлами со степенью 1, ..., с Пт узлами со Степенью т и без узлов со степенями выше т? (Решение этой задачи можно представить в явном виде с помощью факториалов и тем самым существенно обобщить результат упр. 11.)

► 33. [М28] В этом разделе в явном виде дано решение уравнения w = i/ie"" Н-----(-г/ге"",

которое основано на формулах перечисления для некоторых ориентированных лесов. Аналогично покажите, что формула перечисления из упр. 32 позволяет получить решение w уравнения

W ~ Zlltl + Z2ltl= -1-----1- Zrltl"

ЯВНО в виде степенного ряда zi,... ,Zr. (Здесь ei,..., ег - фиксированные неотрицательные целые числа, среди которых по крайней мере одно равно нулю.)

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

Ниже в настоящем разделе мы будем рассматривать схемы бинарного дерева в расширенном виде: добавим к диаграмме дерева специальные узлы в местах, где в исходном дереве присутствуют пустые поддеревья, таким образом, что дерево

примет вид С) ГП Г) Г~) (1)

Полученное дерево назьшается расширенным бинарным деревом (extended binary tree). После добавления квадратных узлов получим более удобную для работы структуру, которая будет довольно часто использоваться в последующих главах. Ясно, что каждый круглый узел имеет двух детей, а каждый квадратный - ни одного (ср. с 2.3-20). Если в дереве имеется п круглых и s квадратных узлов, то в нем имеется также п + s - 1 ребер (поскольку эта диаграмма - свободное дерево). Подсчитывая количество ребер другим способом, т. е. по количеству детей, получим 2п ребер. Отсюда следует, что

s = n+l. (2)

Иначе говоря, количество добавленных "внешних" узлов на единицу больше исходного количества "внутренних" узлов. (Другое доказательство приводится в упр. 2.3.1-14.) Формула (2) справедлива даже для п - 0.

Предположим, что бинарное дерево расширено именно таким образом. Тогда длина внешнего пути дерева (external path length of the tree), E, определяется, как сумма длин путей от корня к каждому узлу, взятая по всем внешним (квадратным) узлам. Длина внутреннего пути дерева (internal path length), I, определяется так же, но суммирование длин путей вьшолняется по внутренним (круглым) узлам. Для дерева (1) длина внешнего пути равна £ = 34-34-2-1-3 + 4-1-4-1-3-1-3 = 25, а длина внутреннего пути равна 7 = 2+1+0 + 2 + 3 + 1+ 2= И. Эти две величины, очевидно, связаны формулой

Е = 1 + 2п, (3)

где п - количество внутренних узлов.

Для доказательства соотношения (3) удалим внутренний узел V, который находится на расстоянии к от корня, где оба ребенка вершины V - внешние узлы. Величина Е при этом уменьшается на 2(к + 1), так как удаляются дети узла V, и в то же время увеличивается на к, так как узел V становится внешним. В целом, изменение величины Е равно -fc - 2, а изменение величины / равно -fc. Далее справедливость формулы (3) доказывается по индукции.

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

(п-1) + (п-2) + --- + 1+0 =

п - п

Можно показать, что "средняя" длина пути для всех бинарных деревьев прямо пропорциональна пфг (см. упр. 5).

Рассмотрим теперь задачу построения бинарного дерева с п узлами, которое обладает минимальной длиной пути. Деревья такого типа имеют большое практическое значение, так как с их пoющью можно сократить до минимума время вьшолнения различных алгоритмов. Ясно, что только один узел (корень) может находиться на нулевом расстоянии от корня. Далее, не более двух узлов может находиться на расстоянии 1 от корня, не более четырех узлов - на расстоянии 2. и т. д. Следовательно, внутренняя длина пути всегда не меньше суммы первых п членов ряда

О, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,... .

Эт} сумму можно вырешить формулой XfciLgfcJ, которая, как нам известно из результата упр. 1.2.4-42, равна

(п"+1)9-2+1+2. q=Mn + l)\

Оптимальное значение (4) равно nlgn + 0(n), так как q = lgn + 0(l). Ясно, что этот результат достигается, например, в дереве следующего типа (здесь представлена схема дерева для п = 12).

Дерево типа (5) называется полным бинарным деревом (complete binary tree) с п внутренними узлами. В общем случае можно перенумеровать внутренние узлы 1,2,. .,п. Эта нумерация удобна тем, что родителем узла fc является узел [fc/2j, а детьми узла fc - узлы 2fc и 2fc + 1. Внешние (концевые) узлы нумеруются соответственно числами от п ч-1 до 2п -I- 1 включительно

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

Рассматриваемые понятия можно обобщить д,ля тернарных, кватернарных и других деревьев более высокого порядка. Определим t-арное дерево (t-ary tree) как множество узлов, которое либо пусто, либо состоит нз узла и t упорядоченных и непересекающихся t-арных деревьев. (Это определение обобщает определение бинарного дерева из раздела 2.3.) Полное тернарное дерево (complete ternary tree) с 12 внутренними узлами имеет такой вид