О 5.60 Измените функцию разделяй и властвуй для поиска максимального элемента в массиве (программа 5.6), чтобы она делила массив на к частей, размер которых различался бы не более чем на 1, рекурсивно находила максимум в каждой части и возвращала максимальный из максимумов.

5.61 Нарисуйте 3-арные и 4-арные деревья, соответствующие использованию /:=3 W к = а ъ рекурсивной конструкции, предложенной в упражнении 5.60, для массива, состоящего из 11 элементов (см. рис. 5.6).

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

1110010110001011000

о 5.63 Упорядоченные деревья эквивалентны согласованным парам круглых скобок: упорядоченное дерево - это либо нуль, либо последовательность упорядоченных деревьев, заключенных в круглые скобки. Нарисуйте упорядоченное дерево, соответствующее строке

((()(() О) ())(() О О))

5.64 Создайте программу для определения того, представляют ли два массива

целочисленных значений между О и Л - 1 изоморфные неупорядоченные деревья, если интерпретируются (как в главе 1) в форме связей типа родительский-дочерний в дереве с узлами, пронумерованными от О до Л- 1. То есть, профамма должна определять, существует ли способ изменения нумерации узлов в одном дереве, чтобы представление в виде массива одного дерева было идентичным представлению в виде массива другого дерева.

5.65 Создайте программу для определения того, представляют ли два бинарных де-

рева изоморфные неупорядоченные деревья.

1> 5.66 Нарисуйте все упорядоченные деревья, которые могли бы представлять дерево, определенное набором ребер 0-1, 1-2, 1-3, 1-4, 4-5.

5.67 Докажите, что если в связанном графе, состоящем из 7V узлов, удаление любого ребра влечет за собой разъединение графа, то он имеет N - 1 ребер и ни одного цикла.

5.5 Математические свойства бинарных деревьев

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

Лемма 5.5 Бинарное дерево с N внутренними узлами имеет N + 1 внешних узлов.

Эта лемма доказывается методом индукции: бинарное дерево без внутренних узлов имеет один внешний узел, следовательно, лемма справедлива для N = 0. Для iV> О любое бинарное дерево с TV внутренними узлами имеет к внутренних узлов в левом поддереве и N-\-k внутренних узлов в правом поддереве для некоторого А: в диапазоне между О и N-1, поскольку корень является внутренним узлом. В соответствии с индуктивным предположением левое поддерево имеет к + 1 внешних узлов, а правое поддерево - N-k внешних узлов, что в сумме составляет N+ 1.

Лемма 5.6 Бинарное дерево с N внутренними узлами имеет 2n связей: N-\ связей с внутренними узлами и N + \ связей с внешними узлами.

В каждом дереве с корнем каждый узел, за исключением корня, имеет единственный родительский узел, и каждое ребро соединяет узел с его родительским узлом; следовательно, существует N-\ связей, соединяющих внутренние узлы. Аналогично, каждый из Л + 1 внешних узлов имеет одну связь со своим единственным родительским узлом.

Характеристики производительности многих алгоритмов зависят не только от количества узлов в связанных с ними деревьях, но и от различных структурных свойств.

Определение 5.6 Уровень (level) узла в дереве на единицу выше уровня его родительского узла (корень размещается на уровне 0). Высота (height) дерева - максимальный из уровней узлов дерева. Длина пути (path length) дерева - сумма уровней всех узлов дерева. Длина внутреннего пути (internal path length) бинарного дерева - сумма уровней всех внутренних узлов дерева. Длина внешнего пути (external path length) бинарного дерева - сумма уровней всех внешних узлов дерева.

Удобный способ вычисления длины пути дерева заключается в суммировании произведений к на число узлов на уровне к для всех к.

Из этих соотношений следуют также простые рекурсивные определения, вытекающие непосредственно из рекурсивных определений деревьев и бинарных деревьев. Например, высота дерева на 1 больше максимальной высоты поддеревьев его корня, а длина пути дерева, имеющего N узлов равна сумме длин путей поддеревьев его корня плюс N-\. Приведенные соотношения также непосредственно связаны с анализом рекурсивных алгоритмов. Например, для многих рекурсивных вычислений высота соответствующего дерева в точности равна максимальной глубине рекурсии, или размеру стека, необходимого для поддержки вычисления.

Лемма 5.7 Длина внешнего пути любого бинарного дерева, имеющего N внутренних узлов, на 2n больше длины внутреннего пути.

Эту лемму можно было бы доказать методом индукции, но есть другое, более наглядное доказательство (которое применимо и для доказательства леммы 5.6). Обратите внимание, что любое бинарное дерево может быть сконструировано при помощи следующего процесса: начните с бинарного дерева, состоящего из одного внешнего узла. Затем повторите следующее Л раз: выберите внешний узел и замените его новым внутренним узлом с двумя дочерними внешними узлами. Если выбранный внешний узел располагается на уровне к, длина внутреннего пути увеличивается на к, но длина внешнего пути увеличивается на А: + 2 (один внешний

узел на уровне к удаляется, но два на уровне к + 1 добавляются). Процесс начинается с дерева, длина внутреннего и внешнего путей которого равны О, и на каждом из шагов длина внешнего пути увеличивается на 2 больше, чем длина внутреннего пути.

Лемма 5.8 Высота бинарного дерева с N внутренними узлами не меньше и не больше N - \.

Худший случай - вырожденное дерево, имеющее только один лист и - 1 связь от корня до листа (см. рис. 5.23). В лучшем случае мы имеем уравновешенное дерево с 2 внутренними узлами на каждом уровне /, за исключением самого нижнего (см. рис. 5.23). Если высота равна h, то должно быть справедливо соотношение

2 < N+ \ < 2

поскольку существует N + 1 внешних узлов. Из этого неравенства следует провозглашенная лемма: в лучшем случае высота равна \gN, округленному до ближайшего целого числа.

Лемма 5.9 Длина внутреннего пути бинарного дерева с N внутренними узлами не меньше чем N]g(N/ А) и не превышает N(N- 1)/ 2.

Худший и лучший случай соответствуют тем же деревьям, отсые упоминались при рассмотрении леммы 5 и показаны на рис. 5.23. В худшем случае дшна внутреннего пути дерева равна 0+l+2+...+(yV-l)=yV(iV-l)/2. В лучшем случае дерево имеет (Л+1) внутренних узлов при высоте, не превышающей bilgTVv. Перемножая эти значения и применяя лемму 5.7, мы получаем предельное значение (yV+l)LlgAJ - 2N < N\g(N/4).

уровень О уровень 1

уровень 4

РИСУНОК 5.23 БИНАРНОЕ ДЕРЕВО С 10 ВНУТРЕННИМИ УЗЛАМИ

Бинарное дерево, показанное вверху, имеет высоту равную 7, длину внутреннего пути равную 31 и длину внешнего пути равную 51. Полностью уравновешенное бинарное дерево (в центре) с 10 внутренними узлами имеет высоту равную 4, длину внутреннего пути равную 19 и длину внешнего пути равную 39 (ни одно двоичное дерево с 10 узлами не может иметь меньшие значения любых из этих параметров). Вырожденное дерево (внизу) с 10 внутренними узлами имеет высоту равную 10, длину внутреннего пути равную 45 и длину внешнего пути равную 65 (ни одно бинарное дерево с 10 узлами не может иметь большие значения любых из этих параметров).

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

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