Рекурсия и деревья

N!=N\cdot(N -1)!, для }N\geq1, причём 0!=1

for ( t = 1, i = 1; i <= N; i++) t *= i;
        

int factorial(int N)
  {
    if (N == 0) return 1;
    return N*factorial(N -1);
  }
        

int puzzle(int N)
  {
    if (N == 1) return 1;
    if (N % 2 == 0)
      return puzzle(N/2);
    else
    return puzzle(3*N+1);
  }
        

int gcd(int m, int n)
  {
    if (n == 0) return m;
    return gcd(n, m % n);
  }
        

Программа 5.4. Рекурсивная программа для вычисления префиксных выражений

Для вычисления префиксного выражения либо осуществляется преобразование числа из ASCII в двоичную форму (в цикле while в конце программы), либо выполняется операция, указанная первым символом выражения, с двумя операндами, которые вычисляются рекурсивно. Эта функция является рекурсивной, однако использует глобальный массив, содержащий выражение и индекс текущего символа выражения. Индекс увеличивается после вычисления каждого подвыражения.

char *a; int i;
int eval()
  { int x = 0;
    while (a[i] == ' ') i++;
    if (a[i] == ' + ')
      { i++; return eval() + eval(); }
    if (a[i] == '*')
      { i++; return eval() * eval(); }
    while ((a[i] >= '0')  (a[i] <= '9'))
      x = 10*x + (a[i++] -'0');
    return x;
  }
        

В принципе, любой цикл при выполнении рекурсивной программы вызовы функций вкладываются один в другой, пока не будет достигнута точка, где вместо рекурсивного вызова выполняется возврат. В большинстве сред программирования такие вложенные вызовы функций реализуются с помощью эквивалента встроенных стеков. В данной главе мы рассмотрим сущность подобного рода реализаций. Глубина рекурсии - это максимальная степень вложенности вызовов функций в ходе вычисления. В общем случае глубина зависит от входных данных. Например, глубина рекурсии в примерах, приведенных на рис 5.2 и рис 5.3, составляет, соответственно, 9 и 4. бедует учитывать, что для работы рекурсивной программы среда программирования задействует стек, размер которого пропорционален глубине рекурсии. При решении сложных задач необходимый для этого стека объем памяти может заставить отказаться от использования рекурсивного решения.

(рис 5.3) Пример вычисления префиксного выражения

Эта вложенная последовательность вызовов функций иллюстрирует работу рекурсивного алгоритма вычисления префиксного выражения. Для простоты здесь показаны аргументы выражения. Сам по себе алгоритм никогда явно не определяет длину строки своих аргументов: вся необходимая информация содержится в начале строки.

Огруктуры данных, построенные из узлов с указателями, рекурсивны по своей природе. Например, рекурсивным является определение связных списков в (определение 3.3). Cледовательно, рекурсивные программы обеспечивают естественные реализации для многих часто используемых функций, работающих с этими структурами данных. Программа 5.5 содержит четыре таких примера. Подобные реализации в книге используются часто - в основном потому, что их гораздо проще понять, чем их нерекурсивные аналоги. Однако при обработке очень больших списков рекурсивные программы, подобные программе 5.5, следует использовать с осторожностью, поскольку глубина рекурсии для таких функций может быть пропорциональна длине списков и, соответственно, требуемый для рекурсивного стека объем памяти может оказаться слишком большим.

Некоторые среды программирования автоматически выявляют и исключают концевую рекурсию (tail recursion), когда последним действием функции является рекурсив -

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

В разделах 5.2 и 5.3 будут рассмотрены два семейства рекурсивных алгоритмов, представляющие важные вычислительные парадигмы. Затем, в разделах 5.4 - 5.7, мы познакомимся с рекурсивными структурами данных, служащими основой для большой группы алгоритмов.

Программа 5.5. Примеры рекурсивных функций для связных списков

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

Первая функция, count, подсчитывает количество узлов в списке. Вторая, traverse, вызывает функцию visit для каждого узла списка, с начала до конца. Обе функции легко реализуются и с помощью цикла for или while. Третья функция, traverseR, не имеет простого итеративного аналога. Она вызывает функцию visit для каждого узла списка, но в обратном порядке.

Четвертая функция, , но в данном случае и x, и t указывают на один и тот же узел.

int count(link x)
  {
    if (x == 0) return 0;
    return 1 + count(x ->next);
  }
void traverse(link h, void visit(link))
  {
    if (h == 0) return;
    visit(h);
    traverse(h ->next, visit);
  }
void traverseR(link h, void visit(link))
  {
    if (h == 0) return;
    traverseR(h ->next, visit); visit(h);
  }
void remove(link x, Item v)
  {
    while (x != 0  x ->item == v)
      { link t = x; x = x ->next; delete t; }
    if (x != 0) remove(x ->next, v);
  }
        

Упражнения

5.1. Напишите рекурсивную программу для вычисления lg(N!).

5.2. Измените программу 5.1 для вычисления N! mod M без риска вызвать переполнение. Попробуйте выполнить программу для M = 997 и N = 103, 104, 105 и 106 , чтобы увидеть, как используемая система программирования обрабатывает рекурсивные вызовы с большой глубиной вложенности.

5.3. Приведите последовательности значений аргумента, получаемых в результате вызова программы 5.2 для каждого из целых чисел от 1 до 9.

5.4. Найдите значение N < 106 , при котором программа 5.2 выполняет максимальное количество рекурсивных вызовов.

5.5.Создайте нерекурсивную реализацию алгоритма Евклида.

5.6. Приведите рисунок, соответствующий рис 5.2, для результата выполнения алгоритма Евклида с числами 89 и 55.

5.7. Определите глубину рекурсии алгоритма Евклида для двух последовательных чисел Фибоначчи (FN и FN+1) .

5.8. Приведите рисунок, соответствующий рис 5.3, для результата вычисления префиксного выражения + * * 12 12 12 144.

5.9. Напишите рекурсивную программу для вычисления постфиксных выражений.

5.10. Напишите рекурсивную программу для вычисления инфиксных выражений, в которых операнды всегда заключены в круглые скобки.

5.11. Напишите рекурсивную программу, которая преобразует инфиксные выражения в постфиксные.

5.12. Напишите рекурсивную программу, которая преобразует постфиксные выражения в инфиксные.

5.13. Напишите рекурсивную программу для решения задачи Иосифа Флавия (см. ).

5.14. Напишите рекурсивную программу, которая удаляет последний узел из связного списка.

5.15. Напишите рекурсивную программу для изменения порядка следования узлов в связном списке на обратный (см. программу 3.7). Совет: используйте глобальную переменную.

Разделяй и властвуй

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

В качестве примера рассмотрим задачу отыскания максимального из N элементов массива a[0], ..., a[N -1]. Эту задачу можно легко выполнить за один проход по массиву:

for (t = a[0], i = 1; i < N; i++)
  if (a[i] > t) t = a[i];
        

Рекурсивное решение типа "разделяй и властвуй ", приведенное в программе 5.6 - также простой (хотя и совершенно иной) алгоритм решения той же задачи; он приведен только для иллюстрации концепции "разделяй и властвуй ".

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

(рис 5.4) Рекурсивный способ отыскания максимума

Эта последовательность вызовов функций иллюстрирует динамику отыскания максимума с помощью рекурсивного алгоритма.

На рис 5.4 показаны рекурсивные вызовы, выполняемые при запуске программы 5.6 для некоторого массива. Структура последовательности вызовов кажется сложной, но обычно об этом можно не беспокоиться - для доказательства правильности работы программы мы полагаемся на метод математической индукции, а для анализа ее производительности используется рекуррентное соотношение.

Как обычно, сам код предлагает проверку правильности вычисления методом индукции:

Он явно и немедленно находит максимальный элемент массива, размер которого равен 1.

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

Более того, рекурсивную структуру программы можно использовать для исследования характеристик ее производительности.

Программа 5.6. Применение принципа "разделяй и властвуй " для отыскания максимума

Эта функция делит массив a[l] , ..., a[r] на массивы a[l] , ..., a[m] и a[m+1], ..., a[r], находит (рекурсивно) максимальные элементы в обеих частях и возвращает больший из них в качестве максимального элемента всего массива. Предполагается, что Item - тип первого класса, для которого операция определена >. Если размер массива является четным числом, обе части имеют одинаковые размеры, а если нечетным, эти размеры различаются на 1.

Item max(Item a[], int l, int r)
  {
    if (l == r) return a[l] ;
    int m = (l+r) /2;
    Item u = max(a, l, m);
    Item v = max(a, m+1, r);
    If (u > v) return u; else return v;
  }
        

Лемма 5.1. Рекурсивная функция, которая делит задачу размера N на две независимые (непустые) части и рекурсивно решает их, вызывает себя менее N раз.

Если одна часть имеет размер к, а другая - N - k, то общее количество рекурсивных вызовов используемой функции равно

TN = Tk + TN - k + 1, при $$$N\geq1$$$; T1 = 0

Решение TN = N - 1 можно получить непосредственно методом индукции. Если сумма размеров частей меньше N, доказательство того, что количество вызовов меньше чем N - 1, вытекает из тех же индуктивных рассуждений. Аналогичными рассуждениями можно подтвердить справедливость данного утверждения и для общего случая (см. упражнение 5.20). $$$\blacksquare$$$

Программа 5.6 - типичный пример для многих алгоритмов вида "разделяй и властвуй ", имеющих совершенно одинаковую рекурсивную структуру, но другие примеры могут отличаться от приведенного в двух аспектах. Во-первых, программа 5.6 выполняет одинаковый объем вычислений для каждого вызова функции, и поэтому ее общее время выполнения линейно. Как мы увидим, другие алгоритмы "разделяй и властвуй " могут выполнять различный объем вычислений для различных вызовов функций, и поэтому для определения общего времени выполнения требуется более сложный анализ. Время выполнения таких алгоритмов зависит от конкретного способа разделения на части. Во -вторых, программа 5.6 - типичный пример алгоритмов "разделяй и властвуй ", для которых сумма размеров частей равна размеру общей задачи. Другие алгоритмы "разделяй и властвуй " могут делить задачу на части, сумма размеров которых меньше или больше размера исходной задачи. Эти алгоритмы тоже относятся к рекурсивным алгоритмам "разделяй и властвуй ", поскольку каждая часть меньше целого, но анализировать их труднее, чем программу 5.6. Мы подробно проанализируем каждый из этих видов алгоритмов по мере их рассмотрения.

Например, алгоритм бинарного поиска, приведенный в разделе 2.6 , является алгоритмом вида "разделяй и властвуй ", который делит задачу пополам, а затем работает только с одной из этих половин. Рекурсивная реализация бинарного поиска будет рассмотрена в .

На рис 5.5 показано содержимое внутреннего стека, который используется средой программирования для реализации вычислений, изображенных на рис 5.4. Приведенная на рисунке модель является идеализированной, но она позволяет понять структуру вычисления по методу "разделяй и властвуй ". Если в программе имеются два рекурсивных вызова, то во время ее выполнения внутренний стек содержит сначала один элемент, соответствующий первому вызову функции во время выполнения (он содержит значения аргументов, локальные переменные и адрес возврата), а затем аналогичный элемент для второго вызова функции. На рис 5.5 показан другой подход - помещение в стек сразу двух элементов с сохранением всех подстеков, которые должны явно создаваться в стеке. Такая организация проясняет структуру вычислений и закладывает основу для более общих вычислительных схем, подобных тем, о которых пойдет речь в разделах 5.6 и 5.8.

На рис 5.6 показана структура алгоритма "разделяй и властвуй " для поиска максимального значения. Эта структура является рекурсивной: верхний узел содержит размер входного массива; структура левого подмассива изображена слева, а правого - справа. Формальное определение и описание структур деревьев такого вида приведены в разделах 5.4 и 5.5. Они облегчают понимание структуры любых программ, в которых используются вложенные вызовы функций, но особенно рекурсивных программ.

(рис 5.5) Пример динамики внутреннего стека

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

(рис 5.6) Рекурсивная структура алгоритма поиска максимума

Алгоритм "разделяй и властвуй "разбивает задачу размером 11 на задачи с размерами 6 и 5, задачу размером 6 - на две задачи с размерами 3 и 3 - и т.д., пока не будет получена задача размером 1 (вверху). Каждый кружок на этих диаграммах означает вызов рекурсивной функции для расположенных непосредственно под ней узлов, связанных с ней линиями (квадратики означают вызовы, в которых рекурсия завершается). На диаграмме в центре показано значение индекса в середине разбиения файла; на нижней диаграмме показано возвращаемое значение.

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

Ни одно рассмотрение рекурсии не будет полным без рассмотрения старинной задачи о ханойских башнях. Имеется три стержня и N дисков, которые помещаются на трех стержнях. Диски различаются размерами и вначале размещаются на одном из стержней от самого большого (диск N) внизу до самого маленького (диск 1) вверху. Задача состоит в перемещении дисков на соседнюю позицию (стержень) при соблюдении следующих правил: (1) одновременно можно переложить только один диск; и (2) ни один диск нельзя положить на диск меньшего размера. Легенда гласит, что конец света наступит тогда, когда некая группа монахов выполнит такую задачу для 40 золотых дисков на трех алмазных стержнях.

Программа 5.7 предоставляет рекурсивное решение этой задачи. Она указывает диск, который должен быть перемещен на каждом шагу, и направление его перемещения (+ означает перемещение на один стержень вправо, или на крайний левый, если текущий стержень крайний справа, а - означает перемещение на один стержень влево, или на крайний правый, если текущий стержень крайний слева). Рекурсия основана на следующей идее: для перемещения показаны перемещения для N = 5 и рекурсивные вызовы для N = 3. Структура алгоритма достаточно очевидна; давайте рассмотрим его подробно.

Во-первых, рекурсивная структура этого решения непосредственно обуславливает количество необходимых перемещений.

Лемма 5.2. Рекурсивный алгоритм "разделяй и властвуй " для задачи о ханойских башнях дает решение, приводящее к 2N - 1 перемещениям.

Как обычно, из кода немедленно следует, что количество перемещений удовлетворяет условию рекуррентности. В данном случае рекуррентная формула похожа на формулу 2.5:

TN = 2TN -1 + 1, при$$$N\geq2$$$, T1 = 1.

Предсказанный результат можно непосредственно проверить методом индукции: мы имеем T(1) = 21 - 1 = 1; и, если для к < N верно T(к) = 2k - 1, то T(N) = 2 (2N -1 - 1) + 1 = 2N - 1. $$$\blacksquare$$$

Программа 5.7. Решение задачи о ханойских башнях

Чтобы переместить башню из дисков вправо, мы перемещаем (рекурсивно) все диски, кроме нижнего, влево, потом перекладываем нижний диск вправо, а затем перемещаем (рекурсивно) башню поверх нижнего диска.

void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N -1,  -d);
    shift(N, d);
    hanoi(N -1,  -d);
  }
        

(рис 5.7) Ханойские башни

На этой схеме показано решение задачи о ханойских башнях с пятью дисками. Мы перемещаем четыре верхних диска влево на одну позицию (левый столбец), затем перекладываем диск 5 вправо, а затем верхние четыре диска перемещаем влево на одну позицию (правый столбец). Приведенная ниже последовательность вызовов функций образует вычисление для трех дисков. Вычисленная последовательность перемещений - +1 -2 +1 +3 +1 -2 +1 - появляется в решении четыре раза (для примера показаны первые семь перемещений).

Если монахи перекладывают по одному диску в секунду, то для завершения работы им потребуется, по меньшей мере, 348 столетий (см. рис 2.1) - разумеется, если они не допускают ошибок. Скорее всего, конец света наступит даже позже этого срока, поскольку, по -видимому, монахи не пользуются программой 5.7 для быстрого выяснения, какой диск нужно переложить следующим. А теперь давайте проанализируем метод, который ведет к простому (не рекурсивному) решению, упрощающему принятие решения. Не хочется помогать монахам, однако этот метод имеет большое значение для множества практически важных алгоритмов.

Чтобы понять решение задачи о ханойских башнях, рассмотрим простую задачу рисования меток на линейке. Каждые 1/2 дюйма на линейке отмечаются черточкой, каждые 1/4 дюйма отмечаются несколько более короткими черточками, 1/8 дюйма - еще более короткими и т.д. Задача состоит в создании программы для рисования этих меток для любого заданного разрешения, при условии, что в нашем распоряжении имеется процедура mark(x, h) для рисования метки высотой h условных единиц в позиции x.

Если требуемое разрешение равно . Рекурсивный метод состоит в следующем. Для помещения меток на интервале он вначале делится на две равные половины. Затем создаются (рекурсивно) более короткие метки в левой половине, в середине помещается длинная метка, и создаются (рекурсивно) более короткие метки в правой половине. На рис 5.8 видно, что с помощью этого метода метки создаются по порядку, слева направо (то есть итеративно) - и проблема заключается в вычислении длин меток. Дерево рекурсии, приведенное на рисунке, помогает понять вычисления: просматривая его сверху вниз, мы видим, что длина меток уменьшается на 1 для каждого рекурсивного вызова функции. Если просматривать дерево в поперечном направлении, мы получаем метки в порядке нанесения, поскольку для каждого данного узла вначале рисуются метки, связанные с вызовом функции слева, затем метка, связанная с данным узлом, а затем метки, связанные с вызовом функции справа.

Программа 5.8. Применение алгоритма "разделяй и властвуй " для рисования линейки

Для отрисовки меток на линейке мы рисуем метки в левой половине, затем самую длинную метку в середине, а затем метки в правой половине. Данная программа предназначена для использования со значением r - l, равным степени 2 - и это свойство сохраняется в ее рекурсивных вызовах (см. упражнение 5.27).

void rule(int l, int r, int h)
  { int m = (l+r)/2;
    if (h > 0)
      {
        rule(l, m, h -1);
        mark(m, h);
        rule(m, r, h -1);
      }
  }
        

Cразу видно, что последовательность длин в точности совпадает с последовательностью перемещаемых дисков при решении задачи о ханойских башнях. Действительно, простым доказательством их идентичности является идентичность рекурсивных программ. То есть для определения перекладываемого диска наши монахи могли бы воспользоваться метками на линейке.

Более того, и решение задачи о ханойских башнях в программе 5.7, и программа рисования линейки в программе 5.8 являются вариантами общей схемы "разделяй и властвуй ", представленной программой 5.6. Все три программы решают задачу размера 2ⁿ, разбивая ее на две задачи размера 2^{n -1}. При отыскании максимума время получения решения линейно зависит от размера входного массива; при рисовании линейки и при решении задачи о ханойских башнях время линейно зависит от размера выходного массива. Обычно считается, что время выполнения задачи о ханойских башнях экспоненциально, хотя объем задачи измеряется количеством дисков, т.е. п.

(рис 5.8) Вызовы функции, рисующие метки на линейке

Эта последовательность вызовов функции вычисляет длины меток для рисования линейки длиной 8, в результате чего наносятся метки 1, 2, 1, 3, 1, 2 и 1.

Рисование меток на линейке с помощью рекурсивной программы не представляет особой сложности, но, может быть, существует более простой способ вычисления длины i -ой метки для любого данного значения показан еще один простой вычислительный процесс, дающий ответ на этот вопрос. Оказывается, i -е число, выводимое и программой решения задачи о ханойских башнях, и программой рисования линейки - просто количество оконечных нулевых разрядов в двоичном представлении i. Это утверждение можно доказать методом индукции по соответствию с формулировкой метода "разделяй и властвуй " для процесса вывода таблицы " -разрядных чисел: достаточно напечатать таблицу (п - 1) -разрядных чисел, каждому из которых предшествует 0, а затем напечатать таблицу (п - 1) -разрядных чисел, каждому из которых предшествует 1 (см. упражнение 5.25).

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

Перемещение маленького диска вправо, если п нечетно (влево, если четно).

Выполнение единственного разрешенного перемещения, не затрагивающего маленький диск.

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

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

Формальное доказательство методом индукции того, что в решении задачи о ханойских башнях каждое второе перемещение является перекладыванием маленького диска (им же все начинается и заканчивается), весьма поучительно: Для n = 1 существует только одно перемещение, затрагивающее маленький диск, следовательно, утверждение подтверждается. При n > 1 из предположения, что утверждение справедливо для n - 1, следует его справедливость и для n: первое решение для n - 1 начинается перекладыванием маленького диска, а второе решение для n - 1 завершается перекладыванием маленького диска - следовательно, решение для n начинается и завершается перекладыванием маленького диска. Перемещение, не затрагивающее маленький диск, вставляется между двумя перемещениями, которые его затрагивают (перекладыванием, завершающим первое решение для n - 1, и перекладыванием, начинающим второе решение для n - 1) - следовательно, свойство, что каждое второе перемещение является перекладыванием маленького диска, остается в силе.

(рис 5.9) Двоичный подсчет и функция рисования линейки

Вычисление функции рисования линейки эквивалентно подсчету количества оконечных нулей в четных N -разрядных числах.

Программа 5.9 - альтернативный способ рисования линейки, на который натолкнуло соответствие с двоичными числами (см. рис 5.10). Эту версию алгоритма называют восходящей (bottom -up) реализацией. Она не является рекурсивной, но определенно навеяна рекурсивным алгоритмом. Эта связь между алгоритмами "разделяй и властвуй " и двоичными представлениями чисел часто помогает найти решение при анализе и разработке усовершенствованных версий, таких как восходящие подходы. Мы будем рассматривать данную возможность, чтобы понять и, возможно, усовершенствовать каждый рассматриваемый алгоритм вида "разделяй и властвуй ".

Восходящий подход предполагает изменение порядка выполнения вычислений при рисовании линейки. На рис 5.11 показан еще один пример, в котором изменен порядок следования трех вызовов функций в рекурсивной реализации. Этот пример соответствует рекурсивному рисованию первоначально описанным способом: нанесение средней метки, затем левой половины, а затем правой. Последовательность нанесения меток выглядит сложной, но является результатом простой перемены мест двух операторов в программе 5.8. Как будет показано в разделе 5.6, взаимосвязь между рис 5.8 и рис 5.11 сродни различию между постфиксными и префиксными арифметическими выражениями.

Программа 5.9. Нерекурсивная программа для рисования линейки

В отличие от программы 5.8, линейку можно нарисовать, вначале изобразив все метки длиной 1, затем все метки длиной 2 и т.д. Переменная t представляет длину меток, а переменная j - количество меток между двумя последовательными метками длиной t. Внешний цикл for увеличивает значение t при сохранении соотношения j = 2 -1. Внутренний цикл for рисует все метки длиной t.

void rule(int l, int r, int h)
  {
    for (int t = 1, j = 1; t <= h; j += j, t++)
    for (int i = 0; l+j+i <= r; i += j+j)
      mark(l+j+i, t);
  }
        

Возможно, нанесение меток в порядке, показанном на рис 5.8, более удобно по сравнению с вычислениями в измененном порядке, которые содержатся в программе 5.9 и приведены на рис 5.11, поскольку в этом случае можно нарисовать линейку произвольной длины. Достаточно представить себе графическое устройство, которое просто непрерывно перемещается от одной метки к следующей. Аналогично, при решении задачи о ханойских башнях мы ограничены последовательностью перемещений, которая должна быть выполнена. Вообще говоря, многие рекурсивные программы основываются на решениях подзадач, которые должны быть выполнены в конкретном порядке. Для других вычислений (см., например, программу 5.6) порядок решения подзадач роли не играет. Для таких вычислений единственным ограничением служит необходимость решения подзадач перед тем, как можно будет решить главную задачу. Понимание того, когда можно изменять порядок вычисления, не только служит ключом к успешной разработке алгоритма, но и во многих случаях оказывает непосредственное практическое влияние. Например, этот вопрос исключительно важен при реализации алгоритмов для работы на параллельных процессорах.

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

Лишь небольшой шаг отделяет рисование линеек от рисования двумерных узоров, похожих на показанный на рис 5.12. Этот рисунок показывает, как простое рекурсивное описание может приводить к сложным на вид вычислениям (см. упражнение 5.30).

(рис 5.10) Рисование линейки в восходящем порядке

Для рисования линейки нерекурсивным методом вначале рисуются все метки длиной 1 и пропускаются позиции, затем рисуются метки длиной 2 и пропускаются остающиеся позиции, затем рисуются метки длиной 3 с пропуском остающихся позиций и т.д.

(рис 5.11) Вызовы функций для рисования линейки (версия с использованием прямого обхода)

Эта последовательность отображает результат нанесения меток перед рекурсивными вызовами, а не между ними.

(рис 5.12) Двумерная фрактальная звезда

Этот фрактал - двумерная версия рис 5.10. Очерченные квадраты на нижнем рисунке демонстрируют рекурсивную структуру вычисления.

Рекурсивно определенные геометрические узоры, наподобие показанного на рис 5.12, иногда называют фракталами. При использовании более сложных примитивов рисования и более сложных рекурсивных функций (особенно рекурсивно определенных функций на вещественной оси и комплексной плоскости) можно получить поразительно разнообразные и сложные узоры. На рис 5.13 приведен еще один пример - звезда Коха, которая определяется рекурсивно следующим образом: звезда Коха порядка 0 - простой выступ, показанный на рис 4.3, а звезда Коха n -го порядка - это звезда Коха порядка п - 1, в которой каждый отрезок заменен звездой порядка 0 соответствующего размера.

Подобно решениям задач рисования линейки и ханойских башен, эти алгоритмы линейны по отношению к количеству шагов, но это количество связано экспоненциальной зависимостью с максимальной глубиной рекурсии (см. упражнения 5.29 и 5.33). Они также могут быть непосредственно связаны с последовательностью натуральных чисел в соответствующей системе счисления (см. упражнение 5.34).

(рис 5.13) Рекурсивная PostScript -программа для рисования фрактала Коха

Это изменение программы PostScript, приведенной на рис 4.3, преобразует результат ее работы в фрактал (см. текст).

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

Бинарный поиск (см. и ) и сортировка слиянием (см. ) - типичные алгоритмы "разделяй и властвуй ", которые обеспечивают гарантированную оптимальную производительность, соответственно, поиска и сортировки. Рекуррентные соотношения демонстрируют сущность вычислений методом "разделяй и властвуй " для каждого алгоритма. (Вывод решений, приведенных в правом столбце, см. в разделах 2.5 и 2.6.) При бинарном поиске задача делится пополам, выполняется одно сравнение, а затем рекурсивный вызов для одной из половин. При сортировке слиянием задача делится пополам, затем выполняется рекурсивная обработка обеих половин, после чего программа выполняет N сравнений. В книге будет рассмотрено множество других алгоритмов, разработанных с применением этих рекурсивных схем.

Основные алгоритмы типа "разделяй и властвуй "

	рекуррентное соотношение	приближенное решение
Бинарный поиск
количество сравнений	CN = CN/2 + 1	lg N
Сортировка слиянием
количество рекурсивных вызовов	AN = 2AN/2 + 1	N
количество сравнений	CN = 2CN/2 + N	NlgN

Быстрая сортировка (см. ) и поиск в бинарном дереве (см. ) представляют важную разновидность базового подхода "разделяй и властвуй ", в которой задача разбивается на подзадачи размеров k - 1 и N - k для некоторого k, определенного во входных данных. При случайных входных данных эти алгоритмы разбивают задачи на подзадачи, размеры которых в среднем вдвое меньше исходного (как в сортировке слиянием или бинарном поиске). Влияние этого различия будет рассмотрено при изучении этих алгоритмов.

Заслуживают внимания и следующие разновидности основной темы: разбиение на части различных размеров, разбиение более чем на две части, разбиение на перекрывающиеся части и выполнение различного объема вычислений в нерекурсивной части алгоритма. В общем случае алгоритмы "разделяй и властвуй " требуют выполнения вычислений для разбиения входного массива на части, либо для объединения результатов обработки двух независимо решенных частей исходной задачи, либо для упрощения задачи после того как половина входного массива обработана. То есть, код может находиться перед, после и между двумя рекурсивными вызовами. Естественно, подобные вариации приводят к созданию более сложных алгоритмов, чем бинарный поиск или сортировка слиянием, и эти алгоритмы труднее анализировать. В данной книге будут рассмотрены многочисленные примеры; к более сложным приложениям и способам анализа мы вернемся в части VIII.

Упражнения

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

5.17. Напишите рекурсивную программу, которая находит максимальный элемент в связном списке.

5.18 Измените программу "разделяй и властвуй " для отыскания максимального элемента в массиве (программа 5.6), чтобы она делила массив размера N на две части, одна из которых имеет размер k=2risN - 1, а вторая - N - к (чтобы размер хотя бы одной части был степенью 2).

5.19. Нарисуйте дерево, которое соответствует рекурсивным вызовам, выполняемым программой из упражнения 5.18 при размере массива 11.

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

5.21. Докажите, что рекурсивное решение задачи о ханойских башнях (программа 5.7) является оптимальным. То есть покажите, что любое решение требует по меньшей мере 2N - 1 перекладываний.

5.22. Напишите рекурсивную программу, которая вычисляет длину i -ой метки на линейке с 2ⁿ - 1 метками.

5.23. Проанализируйте таблицы " -разрядных чисел наподобие приведенной на рис 5.9 и определите свойство i -го числа, определяющего направление i -го перемещения (указанного знаковым битом на рис 5.7) при решении задачи о ханойских башнях.

5.24. Напишите программу, которая выдает решение задачи о ханойских башнях путем заполнения массива, содержащего все перемещения, как сделано в программе 5.9.

5.25. Напишите рекурсивную программу, которая заполняет массив размером n х 2n нулями и единицами таким образом, чтобы массив представлял все n -разрядные числа, как показано на рис 5.9.

5.26. Приведите результаты использования рекурсивной программы рисования линейки (программа 5.8) для следующих значений аргументов: rule(0, 11, 4) , rule(4, 20, 4) и rule(7, 30, 5).

5.27. Докажите следующее свойство программы рисования линейки (программа 5.8): если разность между ее первыми двумя аргументами является степенью 2, то оба ее рекурсивных вызова также обладают этим свойством.

5.28. Напишите функцию, которая эффективно вычисляет количество завершающих нулей в двоичном представлении целого числа.

5.29. Сколько квадратов изображено на рис 5.12 (включая и те, которые скрыты большими квадратами)?

5.30. Напишите рекурсивную программу на C++, результатом которой будет PostScript -программа в форме списка вызовов функций ; функция box рисует квадрат ).

5.31. Напишите восходящую нерекурсивную программу (аналогичную программе 5.9), которая вычерчивает верхнюю часть рис 5.12 способом, описанным в упражнении 5.30.

5.32. Напишите PostScript -программу, вычерчивающую нижнюю часть рис 5.12.

5.33. Сколько прямолинейных отрезков содержит звезда Коха " -го порядка?

5.34. Вычерчивание звезды Коха n -го порядка сводится к выполнению последовательности команд вида "повернуть на а градусов, затем прочертить отрезок длиной 1/3" ". Найдите связь с системами счисления, которая позволяет вычертить звезду путем увеличения значения счетчика и последующего вычисления угла а из этого значения.

5.35. Измените программу рисования звезды Коха, приведенную на рис 5.13, для создания другого фрактала, на основе фигуры, состоящей из 5 линий нулевого порядка, вычерчиваемых смещениями на одну условную единицу в восточном, северном, восточном, южном и восточном направлениях (см. рис 4.3).

5.36. Напишите рекурсивную функцию "разделяй и властвуй " для отображения аппроксимации прямолинейного отрезка в пространстве целочисленных координат для заданных конечных точек. Считайте, что все координаты имеют значения от 0 до M. Совет: вначале поставьте точку вблизи середины сегмента.

Динамическое программирование

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

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

(рис 5.14) Структура рекурсивного алгоритма для вычисления чисел Фибоначчи

Из схемы рекурсивных вызовов для вычисления F8 с помощью стандартного рекурсивного алгоритма видно, как рекурсия с перекрывающимися подзадачами может привести к экспоненциальному возрастанию затрат. В данном случае второй рекурсивный вызов игнорирует вычисление, выполненное во время первого вызова, что приводит к значительным повторным вычислениям, поскольку эффект нарастает в геометрической прогрессии. Рекурсивные вызовы для вычисления F6 = 8 (показаны в правом поддереве корня и в левом поддереве левого поддерева корня) приведены ниже.

И напротив, используя обычный массив, можно легко вычислить первые N чисел Фибоначчи за время, пропорциональное N:

F[0] = 0; F[1] = 1;
for (i = 2; i <= N; i++)
  F[i] = F[i -1] + F[i -2];
        

Числа возрастают экспоненциально, поэтому массив не должен быть большим; например, F45 = 1836311903 - наибольшее число Фибоначчи, которое может быть представлено 32 -разрядным целым, поэтому достаточно использовать массив с 46 элементами.

Этот подход дает непосредственный способ получения численных решений для любых рекуррентных соотношений. В случае с числами Фибоначчи можно обойтись даже без массива и ограничиться только последними двумя значениями (см. упражнение 5.37); однако во многих других случаях часто встречающихся рекуррентных соотношений (см., например, упражнение 5.40) необходим массив для хранения всех известных значений.

Программа 5.10. Числа Фибоначчи (рекурсивная реализация)

Эта программа выглядит компактно и изящно, однако неприменима на практике, поскольку время вычисления FN экспоненциально зависит от N. Время вычисления FN+1 в ф " 1.6 раз больше времени вычисления FN. Например, поскольку ф⁹ > 60, если для вычисления Fn компьютеру требуется около секунды, то для вычисления F_N+9 потребуется более минуты, а для вычисления F_N+18 - более часа.

int F(int i)
  {
    if (i < 1) return 0;
    if (i == 1) return 1;
    return F(i -1) + F(i -2);
  }
        

Рекуррентное соотношение - это рекурсивная функция с целочисленными значениями. Рассуждения, приведенные в предыдущем абзаце, подсказывают, что любую такую функцию можно вычислить, вычисляя все значения функции, начиная с наименьшего, и используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Эта техника называется восходящим динамическим программированием (bottom -up dynamic programming). Она применима к любому рекурсивному вычислению при условии, что есть возможность хранить все ранее вычисленные значения. Такая техника разработки алгоритмов успешно используется для решения широкого круга задач. Так что обратите внимание на эту простую технологию, которая может изменить время выполнения алгоритма с экспоненциального на линейное!

Нисходящее динамическое программирование (top -down dynamic programming) - еще более простая техника, которая позволяет автоматически выполнять рекурсивные функции при том же (или меньшем) количестве итераций, что и в восходящем динамическом программировании. При этом рекурсивная программа должна (заключительным действием) сохранять каждое вычисленное ей значение и (первым действием) проверять эти значения во избежание повторного вычисления любого из них. Программа 5.11 - результат механического преобразования программы 5.10, в которой нисходящее динамическое программирование позволило уменьшить время выполнения до линейного.

На рис 5.15 демонстрируется радикальное уменьшение количества рекурсивных вызовов, достигнутое этим простым автоматическим изменением. Иногда нисходящее динамическое программирование называют также мемоизацией (memoization).

В качестве более сложного примера рассмотрим задачу о ранце: вор, грабящий сейф, находит в нем N видов предметов различных размеров и ценности, но имеет только небольшой ранец емкостью M, в котором может унести награбленное. Задача заключается в том, чтобы определить комбинацию предметов, которые вор должен уложить в ранец, чтобы общая стоимость похищенного оказалась наибольшей.

Программа 5.11. Числа Фибоначчи (динамическое программирование)

Сохранение вычисляемых значений в статическом массиве (элементы которого в C++ инициализируются 0) позволяет явно исключить любые повторные вычисления. Эта программа вычисляет Fn за время, пропорциональное N, что существенно отличается от времени 0(ф^N), которое требуется для вычислений программе 5.10.

int F(int i)
  { static int knownF[maxN];
    if (knownF[i] != 0) return knownF[i];
    int t = i;
    if (i < 0) return 0;
    if (i > 1) t = F(i -1) + F(i -2);
    return knownF[i] = t;
  }
        

(рис 5.15) Применение нисходящего динамического программирования для вычисления чисел Фибоначчи

Из этой схемы рекурсивных вызовов, выполненных для вычисления F ₈ методом нисходящего динамического программирования, видно, как сохранение вычисленных значений снижает затраты с экспоненциального (см. рис 5.14) до линейного.

(рис 5.16) Пример задачи о ранце

Входными данными задачи о ранце (вверху) являются емкость ранца и набор предметов различных размеров (которые представлены значениями на горизонтальной оси) и стоимости (значения на вертикальной оси). На этом рисунке показаны четыре различных способа заполнения ранца, размер которого равен 17; два из этих способов дают максимальную суммарную стоимость, равную 24.

Например, при наличии типов предметов, представленных на рис 5.16, вор, располагающий ранцем, размер которого равен 17, может взять только пять (но не шесть) предметов A общей стоимостью 20, или предметы D и E суммарной стоимостью 24, или одно из множества других сочетаний. Наша цель - найти эффективный алгоритм для определения оптимального решения при любом заданном наборе предметов и вместимости ранца.

Решения задачи о ранце важны во многих приложениях. Например, транспортной компании может понадобиться определение наилучшего способа загрузки грузовика или транспортного самолета. В подобных приложениях могут встречаться и другие варианты этой задачи: например, может быть ограничено количество элементов каждого вида или могут быть доступны два грузовика. Многие из таких вариантов можно решить с помощью того же подхода, который будет рассмотрен ниже для решения только что сформулированной базовой задачи, однако бывают и гораздо более сложные варианты. Существует тонкая грань между решаемыми и нерешаемыми задачами этого типа, но об этом речь пойдет в части 8.

В рекурсивном решении задачи о ранце при каждом выборе предмета мы предполагаем, что можем (рекурсивно) определить оптимальный способ заполнения оставшегося места в ранце. Если объем ранца равен cap, то для каждого доступного элемента i определяется общая стоимость элементов, которые можно было бы унести, укладывая i -й элемент в ранец при оптимальной упаковке остальных элементов. Эта оптимальная упаковка - просто упаковка, которая определена (или будет определена) для меньшего ранца объемом cap -items[i].size. Здесь используется следующий принцип: оптимальные принятые решения в дальнейшем не требуют пересмотра. Когда установлено, как оптимально упаковать ранцы меньших размеров, эти задачи не требуют повторного исследования независимо от следующих элементов.

Программа 5.12 - прямое рекурсивное решение, которое основано на приведенных рассуждениях. Эта программа также неприменима для решения реальных задач, поскольку из -за большого объема повторных вычислений (см. рис 5.17) время решения связано с количеством элементов экспоненциально. Но для решения задачи можно автоматически задействовать нисходящее динамическое программирование - и получить программу 5.13. Как и ранее, эта техника исключает все повторные вычисления (см. рис 5.18).

Программа 5.12. Задача о ранце (рекурсивная реализация)

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

typedef struct { int size; int val; } Item;
        

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

int knap(int cap)
  { int i, space, max, t;
    for (i = 0, max = 0; i < N; i++)
      if ((space = cap -items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max)
          max = t;
    return max;
  }
        

Программа 5.13. Задача о ранце (динамическое программирование)

Эта механическая модификация программы 5.12 снижает время выполнения с экспоненциального до линейного. Мы просто сохраняем любые вычисленные значения функции, а затем вместо выполнения рекурсивных вызовов выбираем сохраненные значения, когда они требуются (используя специальный признак для представления неизвестных значений). Индекс элемента сохраняется, поэтому при желании всегда можно восстановить содержимое ранца после вычисления: itemKnown[M] находится в ранце, остальное содержимое совпадает с оптимальной упаковкой ранца размера M -itemKnown[M]. size, следовательно, в ранце находится itemKnown[M -items[M].size] и т.д.

int knap(int M)
  { int i, space, max, maxi = 0, t;
    if (maxKnown[M] != unknown) return maxKnown[M];
    for (i = 0, max = 0; i < N; i++)
      if ((space = M -items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max)
          { max = t; maxi = i; }
    maxKnown[M] = max; itemKnown[M] = items[maxi];
    return max;
  }
        

(рис 5.17) Рекурсивная структура алгоритма решения задачи о ранце

Это дерево представляет структуру рекурсивных вызовов простого рекурсивного алгоритма решения задачи о ранце, реализованного в программе 5.12. Число в каждом узле означает оставшееся свободное место в ранце. Недостатком алгоритма является то же экспоненциальное время выполнения из -за большого объема повторных вычислений, требуемых для решения перекрывающихся подзадач, что и при вычислении чисел Фибоначчи (см. рис 5.14).

(рис 5.18) Применение метода нисходящего динамического программирования для реализации алгоритма решения задачи о ранце

Как и в случае вычисления чисел Фибоначчи, техника сохранения известных значений уменьшает затраты алгоритма с экспоненциального (см. рис 5.17) до линейного.

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

Лемма 5.3. Динамическое программирование снижает время выполнения рекурсивной функции до не более чем суммарного времени, необходимого на вычисление функции для всех аргументов, меньших или равных данному аргументу, при условии, что затраты на рекурсивный вызов постоянны.

См. упражнение 5.50. $$$\blacksquare$$$

Применительно к задаче о ранце из леммы следует, что время выполнения пропорционально произведению NM. Таким образом, задача о ранце легко поддается решению, когда емкость ранца не очень велика; для очень больших емкостей время и требуемый объем памяти могут оказаться недопустимо большими.

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

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

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

оно представляет собой механическую трансформацию естественного решения задачи;

порядок решения подзадач определяется сам собой;

может не потребоваться решение всех подзадач.

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

Однако необходимо учитывать следующий важный момент: динамическое программирование становится неэффективным, когда количество возможных значений функции, которые могут потребоваться, столь велико, что мы не можем себе позволить их сохранять (при нисходящем программировании) или вычислять предварительно (при восходящем программировании). Например, если в задаче о ранце объем ранца и размеры элементов - 64 -разрядные величины или числа с плавающей точкой, значения уже невозможно сохранять путем их индексирования в массиве. Это не просто небольшое неудобство, это принципиальная трудность. Для подобных задач пока не известно ни одного приемлемого решения; как будет показано в части 8, имеются веские причины считать, что эффективного решения нет вообще.

Динамическое программирование - это техника разработки алгоритмов, которая рассчитана в первую очередь на решение сложных задач того вида, который будет рассмотрен в частях V - VIII. Большинство алгоритмов, рассмотренных в частях II - IV, представляют собой реализацию методов "разделяй и властвуй " с не перекрывающимися подзадачами, и основное внимание было уделено скорее субквадратичной или сублинейной производительности, чем субэкспоненциальной. Однако нисходящее динамическое программирование является базовой техникой разработки эффективных реализаций рекурсивных алгоритмов, которая присутствует в арсенале средств любого, кто принимает участие в создании и реализации алгоритмов.

Упражнения

5.37. Напишите функцию, которая вычисляет F_N mod M, используя для промежуточных вычислений постоянный объем памяти.

5.38. Каково наибольшее значение N, для которого F_N может быть представлено в виде 64 -разрядного целого числа?

5.39. Нарисуйте дерево, которое соответствует рис 5.15 для случая, когда рекурсивные вызовы в программе 5.11 поменяны местами.

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

Pn = LN/ 2j + P Ln/ 2j + P n2i, для N > 1, при P0 = 0.

Нарисуйте график зависимости PN - N IgN/ 2 от N для 0 < N < 1024.

5.41. Напишите функцию, в которой восходящее динамическое программирование используется для решения упражнения 5.40.

5.42. Нарисуйте дерево, которое соответствует рис 5.15 для функции из упражнения 5.41 при вызове с аргументом N = 23.

5.43. Нарисуйте график зависимости от N количества рекурсивных вызовов, выполняемых функцией из упражнения 5.41 для вычисления PN при 0 < N < 1024. (При этом для каждого значения N программа должна запускаться заново.)

5.44. Напишите функцию, в которой восходящее динамическое программирование используется для вычисления значения CN, определяемого рекуррентным соотношением

CN = N + N ? (кj + CN_k), для N > 1, при C0 = 1.

N 1< к < N

5.45. Напишите функцию, в которой нисходящее динамическое программирование применяется для решения упражнения 5.44.

5.46. Нарисуйте дерево, которое соответствует рис 5.15 для функции из упражнения 5.45 при вызове с аргументом N = 23.

5.47. Нарисуйте график зависимости от N количества рекурсивных вызовов, выполняемых функцией из упражнения 5.45 для вычисления CN при 0 < N < 1024. (При этом для каждого значения N программа должна запускаться заново.)

5.48. Приведите содержимое массивов maxKnown и itemKnown, вычисленное программой 5.13 для вызова knap(17) с элементами, приведенными на рис 5.16.

5.49. Приведите дерево, соответствующее рис 5.18, если элементы рассматриваются в порядке уменьшения их размеров.

5.50. Докажите лемму 5.3.

5.51. Напишите функцию, решающую задачу о ранце, с помощью варианта программы 5.12, в котором применяется восходящее динамическое программирование.

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

5.53. Напишите функцию, которая решает задачу о ранце с помощью варианта рекурсивного решения, описанного в упражнении 5.52, в котором применяется восходящее динамическое программирование.

5.54. Воспользуйтесь динамическим программированием для решения упражнения 5.4. Наблюдайте за общим количеством сохраняемых вызовов функций.

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

Деревья

Деревья - это математическая абстракция, играющая главную роль при разработке и анализе алгоритмов, поскольку

деревья используются для описания динамических свойств алгоритмов;

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

Мы уже встречались с примерами обоих применений деревьев. В были разработаны алгоритмы для решения задачи связности, которые основаны на древовидных структурах, а в разделах 5.2 и 5.3 структура вызовов рекурсивных алгоритмов была описана с помощью древовидных структур.

Мы часто встречаемся с деревьями в повседневной жизни - это основное понятие очень хорошо знакомо. Например, многие люди графически обозначают связь предков и наследников в виде генеалогического дерева; как мы увидим, значительная часть терминов заимствована именно из этой области. Еще один пример - организация спортивных турниров; в частности, исследованием этого применения занимался Льюис Кэрролл. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение напоминает иерархическое разделение, характерное для алгоритмов "разделяй и властвуй ". Четвертым примером служит дерево синтаксического разбора предложения английского (или любого другого языка) на составляющие его части; такие деревья тесно связаны с обработкой компьютерных языков, как описано в части V. Типичный пример дерева - в данном случае описывающего структуру глав этой книги - показан на рис 5.19. Далее в книге нам встретится и множество других примеров применения деревьев.

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

Существует множество различных типов деревьев, и важно понимать различие между абстракцией и конкретным представлением, с которым выполняется работа для данного приложения. Поэтому мы подробно рассмотрим различные типы деревьев и их представления. Рассмотрение начнется с определения деревьев как абстрактных объектов и с введения большей части основных связанных с ними терминов. Мы неформально рассмотрим различные необходимые нам типы деревьев в порядке сужения этого понятия:

Деревья

Деревья с корнем

Упорядоченные деревья

M -арные и бинарные деревья

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

Дерево (tree) - это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) - это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) - это связь между двумя вершинами. Путь (path) в дереве - это список отдельных вершин, в котором последовательные вершины соединены ребрами дерева. Определяющее свойство дерева - существование только одного пути, соединяющего любые два узла. Если между какой -либо парой узлов существует более одного пути, или если между какой -либо парой узлов путь отсутствует, то это граф, а не дерево. Несвязанное множество деревьев называется лесом (forest).

Дерево с корнем (rooted) - это дерево, в котором один узел назначен корнем (root) дерева. В компьютерных науках термин дерево обычно применяется к деревьям с корнем, а термин свободное дерево (free tree) - к более общим структурам, описанным в предыдущем абзаце. В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов.

(рис 5.19) Дерево

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

(рис 5.20) Типы деревьев

На этих схемах приведены примеры бинарного дерева (вверху слева), тернарно го дерева (вверху справа), дерева с корнем (внизу слева) и свободного дерева (внизу справа).

Существует только один путь между корнем и каждым из других узлов дерева. Данное определение никак не определяет направление ребер; и в зависимости от конкретной ситуации можно считать, что все ребра указывают или от корня, или к корню. Обычно деревья рисуются с корнем вверху (хотя поначалу это соглашение кажется неестественным) и говорят, что узел у располагается под узлом x (а x располагается над у), если x находится на пути от у к корню (т.е., у находится под х, как нарисовано на странице, и соединяется с х путем, который не проходит через корень). Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом (parent); узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами (child). Иногда аналогия с генеалогическими деревьями распространяется дальше, и тогда говорят о " бабушках " (grand parent) или " сестрах " (sibling) данного узла.

Узлы, не имеющие дочерних узлов, называются листьями (leaf) или терминальными (оконечными, terminal) узлами. И, соответственно, узлы, имеющие хотя бы один дочерний узел, иногда называются нетерминальными (nonterminal) узлами. В этой главе мы уже встречались с различным применением этих типов узлов. В деревьях, которые использовались для представления структуры вызовов рекурсивных алгоритмов (например, на рис 5.14), нетерминальные узлы (кружки) представляют вызовы функций с рекурсивными вызовами, а терминальные узлы (квадратики) представляют вызовы функций без рекурсивных вызовов.

В некоторых приложениях способ упорядочения дочерних узлов каждого узла имеет значение; в других это не важно. Упорядоченное (ordered) дерево - это дерево с корнем, в котором определен порядок следования дочерних узлов каждого узла. Упорядоченные деревья - естественное представление: ведь при рисовании дерева дочерние узлы размещаются в определенном порядке. Действительно, многие другие конкретные представления имеют аналогично предполагаемый порядок; например, обычно это различие имеет значение при работе с компьютерными представлениями деревьев.

Если каждый узел должен иметь конкретное количество (M) дочерних узлов, расположенных в конкретном порядке, мы имеем M -арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда внешние узлы можно задействовать в качестве фиктивных, чтобы на них ссылались узлы, не имеющие должного количества дочерних узлов. В частности, простейшим типом M -арного дерева является бинарное дерево. Бинарное дерево (binary tree) - это упорядоченное дерево, состоящее из узлов двух типов: внешних узлов без дочерних узлов и внутренних узлов, каждый из которых имеет ровно два дочерних узла. Поскольку два дочерних узла каждого внутреннего узла упорядочены, можно говорить о левом дочернем узле (left child) и правом дочернем узле (right child) внутренних узлов. Каждый внутренний узел должен иметь и левый, и правый дочерние узлы, хотя один из них или оба могут быть внешними узлами. Лист в M -арном дереве - это внутренний узел, все дочерние узлы которого являются внешними.

Все это общая терминология. Далее рассматриваются формальные определения, представления и приложения в порядке расширения понятий:

бинарные и M -арные деревья

упорядоченные деревья

деревья с корнем

свободные деревья

Начнем с наиболее специфической абстрактной структуры - как мы увидим, это позволит подробно рассмотреть конкретные представления.

Определение 5.1. Бинарное дерево - это либо внешний узел, либо внутренний узел, связанный с (упорядоченной - прим. перев.) парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.

Из этого определения понятно, что само бинарное дерево - абстрактное математическое понятие. При работе с компьютерным представлением мы работаем лишь с одной конкретной реализацией этой абстракции. Эта ситуация не отличается от представления действительных чисел значениями типа float, целых чисел значениями типа int и т.д. Когда мы рисуем дерево с узлом в корне, связанным ребрами с левым поддеревом, расположенным слева, и с правым поддеревом, расположенным справа, мы выбираем удобное конкретное представление. Существует множество различных способов представления бинарных деревьев (см., например, упражнение 5.62), которые поначалу несколько шокируют, но если учесть абстрактный характер определения, они вполне допустимы.

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

struct node { Item item; node *l, *r; }
typedef node *link;
        

Это просто код C++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы; указатели на узлы называются также ссылками. Так, например, абстрактная операция переход к левому поддереву реализуется с помощью обращения через указатель наподобие x = x ->l.

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

(рис 5.21) Представление бинарного дерева

В стандартном представлении бинарного дерева используются узлы с двумя ссылками: левая указывает на левое поддерево, а правая - на правое поддерево. Пустые ссылки соответствуют внешним узлам.

Из -за наличия такого множества различных возможных представлений можно было бы разработать АТД бинарного дерева, который позволяет инкапсулировать важные для нас операции и отделить использование от реализации этих операций. В данной книге такой подход не используется, поскольку

чаще всего будет использоваться представление с двумя ссылками;

деревья будут применяться для реализации АТД более высокого уровня, и мы хотим сосредоточить внимание на этих АТД;

эффективность алгоритмов может зависеть от конкретного представления - это обстоятельство может быть упущено в АТД.

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

Изучение связных списков мы начали с рассмотрения элементарных операций вставки и удаления узлов (см. рис 3.3 и рис 3.4). При использовании стандартного представления бинарных деревьев такие операции совсем не обязательно будут элементарными из -за наличия второй ссылки. Если нужно удалить узел из бинарного дерева, то возникает принципиальная проблема наличия двух дочерних узлов, с которыми нужно что -то делать после удаления узла, и только одного родительского. Существуют три естественных операции, для которых подобное осложнение не возникает: вставка нового узла в нижнюю часть дерева (замена пустой ссылки ссылкой на новый узел), удаление листа (замена ссылки на него пустой ссылкой) и объединение двух деревьев посредством создания нового корня, левая ссылка которого указывает на одно дерево, а правая - на другое. Эти операции интенсивно используются при работе с бинарными деревьями.

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

Обычно узлы в M -арных деревьях представляются либо в виде структур с M именованными ссылками (как в бинарных деревьях), либо в виде массивов M ссылок. Например, в главе 15 рассмотрены 3 -арные (или тернарные) деревья, в которых используются структуры с тремя именованными ссылками (левой, средней и правой), каждая из которых имеет специальное значение для связанных с этими деревьями алгоритмов. В остальных случаях вполне годится хранение ссылок в массивах, поскольку значение M фиксировано - хотя, как мы увидим, при использовании такого представления нужно внимательно следить за объемом использованной памяти.

Определение 5.3. Дерево (называемое также упорядоченным деревом) - это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется лесом.

Различие между упорядоченными деревьями и M -арными деревьями состоит в том, что узлы в упорядоченных деревьях могут иметь любое количество дочерних узлов, а узлы в M -арных деревьях должны иметь точно M дочерних узлов. Иногда, если нужно различать упорядоченные и M -арные деревья, используется термин обобщенное дерево (general tree).

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

(рис 5.22) Представление дерева

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

Лемма 5.4. Существует взаимно однозначное соответствие между бинарными деревьями и упорядоченными лесами.

Это соответствие показано на рис 5.22. Любой лес можно представить в виде бинарного дерева, в котором левая ссылка каждого узла указывает на его левый дочерний узел, а правая ссылка каждого узла - на сестринский узел, расположенный справа. $$$\blacksquare$$$

Определение 5.4. Дерево с корнем (или неупорядоченное дерево) - это узел (называемый корнем), связанный с мультимножеством деревьев с корнем. (Такое мультимножество называется неупорядоченным лесом.)

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

Неупорядоченное дерево можно представить в компьютере упорядоченным деревом; нужно лишь осознавать, что одно и то же неупорядоченное дерево может быть представлено несколькими различными упорядоченными деревьями. Хотя обратная задача - определение того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма деревьев) - подается решению с трудом.

Наиболее общим видом деревьев является дерево, в котором не выделен корневой узел. Например, этим свойством обладают остовные деревья, полученные в результате работы алгоритмов связности из . Для правильного определения неупорядоченных деревьев без корня, т.е. свободных деревьев, потребуется начать с определения графов (graph). Определение 5.5. Граф - это множество узлов вместе с множеством ребер, которые соединяют пары отдельных узлов (причем любая пара узлов соединяется не более чем одним ребром).

Из любого узла можно перейти вдоль ребра до другого узла, от этого - к следующему и т.д. Последовательность ребер, ведущая от одного узла до другого, когда ни один узел не посещается дважды, называется простым путем (simple path). Граф является связным (connected), если для любой пары узлов существует связывающий их простой путь. Простой путь, у которого первый и последний узел совпадают, называется циклом (cycle).

Каждое дерево является графом, а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому из следующих четырех условий:

Граф имеет N - 1 ребер и ни одного цикла.

Граф имеет N - 1 ребер и является связным.

Каждую пару вершин в графе соединяет только один простой путь.

Граф является связным, но перестает быть таковым при удалении любого ребра.

Любое из этих условий - необходимое и достаточное условие для выполнения остальных трех. Формально для определения свободного дерева следует выбрать одно из них; но мы, отбросив формальности, считаем определением все условия вместе.

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

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

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

Упражнения

5.56. Приведите представления свободного дерева, показанного на рис 5.20, в форме дерева с корнем и бинарного дерева.

5.57. Определите количество различных способов представления свободного дерева, показанного на рис 5.20, в форме упорядоченного дерева.

5.58. Нарисуйте три упорядоченных дерева, которые изоморфны упорядоченному дереву, показанному на рис 5.20. Это значит, должна существовать возможность преобразования всех четырех деревьев одного в другое путем обмена дочерних узлов.

5.59. Допустим, деревья содержат элементы, для которых определена операция ==. Напишите рекурсивную программу, которая удаляет в бинарном дереве все листья, содержащие элементы, равные данному (см. программу 5.5).

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

5.61. Нарисуйте 3 -арные и 4 -арные деревья для случаев ).

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

1110010110001011000

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

( ( ( ) ( ( ) ( ) ) ( ) ) ( ( ) ( ) ( ) ) )

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

5.65. Напишите программу для определения того, являются ли два бинарных дерева изоморфными неупорядоченными деревьями.

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

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

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

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

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

Лемма 5.6. Бинарное дерево с N внутренними узлами имеет 2N ссылок: N - 1 ссылок на внутренние узлы и N + 1 ссылок на внешние узлы.

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

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

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

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

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

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

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

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

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

$$$$2^{h -1}<N+1\leq2^{h}$$$$

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

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

Худший и лучший случай соответствуют тем же деревьям, которые упоминались при доказательстве леммы 5.8 и показаны на рис 5.23. В худшем случае длина внутреннего пути дерева равна 0 + 1 + 2 + ... + (N - 1) = N(N - 1)/2. В лучшем случае дерево имеет N + 1 внешних узлов при высоте, не превышающей $$$\lfloor lgN\rfloor$$$. Перемножив эти значения и применив лемму 5.7, получим предельное значение$$$(N+1)\lfloor lgN\rfloor -2N<Nlg(N/4)$$$ . $$$\blacksquare$$$

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

В и будут рассмотрены структуры данных, основанные на уравновешенных деревьях.

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

(рис 5.23) Три бинарных дерева с 10 внутренними узлами

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

Упражнения

5.68. Сколько внешних узлов существует в M -арном дереве с N внутренними узлами? Используйте свой ответ для определения объема памяти, необходимого для представления такого дерева, если считать, что каждая ссылка и каждый элемент занимает одно слово памяти.

5.69. Приведите верхнее и нижнее граничные значения высоты M -арного дерева с N внутренними узлами.

5.70. Приведите верхнее и нижнее граничные значения длины внутреннего пути M -арного дерева с N внутренними узлами.

5.71. Приведите верхнее и нижнее граничные значения количества листьев в бинарном дереве с N узлами.

5.72. Покажите, что если уровни внешних узлов в бинарном дереве различаются на константу, то высота дерева составляет O(logN).

5.73. Дерево Фибоначчи высотой ). Выразите высоту и длину внешнего пути для дерева Фибоначчи высотой n в виде функции от N (количество узлов в дереве).

5.74. Дерево вида "разделяй и властвуй ", состоящее из N узлов - это бинарное дерево с корнем, обозначенным N, деревом "разделяй и властвуй " из$$$\lfloor N/2\rfloor$$$ узлов в одном поддереве и деревом "разделяй и властвуй " из$$$\lceil N/2\rceil$$$ узлов в другом. (Дерево "разделяй и властвуй " показано на рис 5.6.) Нарисуйте дерево "разделяй и властвуй " с 11, 15, 16 и 23 узлами.

5.75. Докажите методом индукции, что длина внутреннего пути дерева вида "разделяй и властвуй " находится в пределах между N lgN и N lgN + N.

5.76. Дерево вида "объединяй и властвуй ", состоящее из N узлов - это бинарное дерево с корнем, обозначенным N, деревом "объединяй и властвуй " из$$$\lfloor N/2\rfloor$$$ узлов в одном поддереве и деревом "объединяй и властвуй " из$$$\lceil N/2\rceil$$$ узлов в другом (см. упражнение 5.18). Нарисуйте дерево "объединяй и властвуй " с 11, 15, 16 и 23 узлами.

5.77. Докажите методом индукции, что длина внутреннего пути дерева вида "объединяй и властвуй " находится в пределах между N lgN и N lgN + N.

5.78. Полное (complete) бинарное дерево - это дерево, в котором заполнены все уровни, кроме, возможно, последнего, который заполняется слева направо, как показано на рис 5.24. Докажите, что длина внутреннего пути полного дерева с N узлами лежит в пределах между N lgN и N lgN + N.

(рис 5.24) Полные бинарные деревья с семью и десятью внутренними узлами

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

Обход дерева

Прежде чем приступить к изучению алгоритмов, в которых создаются бинарные деревья и деревья общего вида, рассмотрим алгоритмы для реализации самой основной функции обработки деревьев - обхода дерева (tree traversal): имея указатель на дерево, требуется систематически обработать все узлы в дереве. В связном списке переход от одного узла к другому выполняется по единственной ссылке; однако в случае деревьев придется принимать решения, поскольку может существовать несколько ссылок для перехода.

Начнем рассмотрение с обхода бинарных деревьев.

В случае со связными списками имелись две основные возможности (см. программу 5.5): обработать узел, а затем перейти по ссылке (посещение узлов в прямом порядке), или перейти по ссылке связи, а затем обработать узел (в этом случае узлы посещаются в обратном порядке). Узлы бинарных деревьев содержат две ссылки и, следовательно, возможны три основных порядка посещения узлов:

Прямой обход (сверху вниз), при котором посещается узел, а затем левое и правое поддеревья

Поперечный обход (слева направо), при котором посещается левое поддерево, потом узел, а затем правое поддерево

Обратный обход (снизу вверх), при котором посещаются левое и правое поддеревья, а затем узел.

Эти методы можно легко реализовать с помощью рекурсивной программы (программа 5.14), которая является непосредственным обобщением программы 5.5 обхода связного списка. Для реализации обходов в другом порядке достаточно соответствующим образом переставить вызовы функций в программе 5.14. Примеры посещения узлов дерева при использовании каждого из порядков обхода показаны на рис 5.26. На рис 5.25 приведена последовательность вызовов функций, которые выполняются при вызове программы 5.14 для дерева из рис 5.26.

(рис 5.25) Вызовы функций при прямом обходе

Эта последовательность вызовов функций определяет прямой обход для примера дерева, показанного на рис 5.26.

С этими базовыми рекурсивными процессами, на которых основываются различные методы обхода дерева, мы уже встречались в рекурсивных программах вида "разделяй и властвуй " (см. рис 5.8 и 5.11) и в арифметических выражениях. Например, выполнение прямого обхода соответствует рисованию вначале метки на линейке, а затем выполнению рекурсивных вызовов (см. рис 5.11); выполнение поперечного обхода соответствует перекладыванию самого большого диска в решении задачи о ханойских башнях между рекурсивными вызовами, которые перемещают все остальные диски; выполнение обратного обхода соответствует вычислению постфиксных выражений и т.д.

Программа 5.14. Рекурсивный обход дерева

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

void traverse(link h, void visit(link))
  {
    if (h == 0) return;
    visit(h);
    traverse(h ->l, visit);
    traverse(h ->r, visit);
  }
        

(рис 5.26) Порядки обхода дерева

Эти последовательности показывают порядок посещения узлов для прямого (слева), поперечного (в центре) и обратного (справа) обхода дерева.

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

Полезно также рассмотреть нерекурсивные реализации, в которых используется явный стек. Для простоты мы начнем с рассмотрения абстрактного стека, который может содержать как узлы, так и деревья, и вначале содержит дерево, которое нужно обойти. Затем выполняется цикл, в котором выталкивается и обрабатывается верхний элемент стека, и который продолжается, пока стек не опустеет. Если вытолкнутое содержимое является элементом, мы посещаем его; а если это дерево, мы выполняем последовательность операций вталкивания, которая зависит от требуемого порядка:

При прямом обходе заносится правое поддерево, затем левое поддерево, а затем узел.

При поперечном обходе заносится правое поддерево, затем узел, а затем левое поддерево.

При обратном обходе заносится узел, затем правое поддерево, а затем левое поддерево.

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

В предыдущем абзаце описана концептуальная схема, охватывающая три метода обхода дерева, однако реализации, используемые на практике, несколько проще.

(рис 5.27) Содержимое стека для алгоритмов обхода дерева

Эти последовательности отражают содержимое стека при прямом (слева), поперечном (в центре) и обратном (справа) обходе дерева (см. рис 5.26) для идеализированной модели вычислений, аналогичной использованной в примере на рис 5.5, когда элемент и два его поддерева помещаются в стек в указанном порядке.

Например, при выполнении прямого обхода узлы заносить в стек не обязательно (поскольку вначале посещается корень каждого выталкиваемого дерева). Поэтому можно воспользоваться простым стеком, который содержит элементы только одного типа (ссылки на деревья), как это сделано в нерекурсивной реализации в программе 5.15. Системный стек, поддерживающий работу рекурсивной программы, содержит адреса возврата и значения аргументов, а не элементы или узлы, но фактическая последовательность выполнения вычислений (посещения узлов) для рекурсивного метода и метода с использованием стека остается одинаковой.

Четвертая естественная стратегия обхода - просто посещение узлов дерева в порядке, в котором они нарисованы на странице - сверху вниз и слева направо. Этот метод называется обходом по уровням (level -order), поскольку все узлы каждого уровня посещаются вместе, по порядку. Посещение узлов дерева, показанного на рис 5.26, при обходе по уровням показано на рис 5.28.

(рис 5.28) Обход по уровням

Эта последовательность показывает результат посещения узлов дерева в порядке сверху вниз и слева направо.

Интересно, что обход по уровням можно получить, заменив в программе 5.15 стек на очередь, что демонстрирует программа 5.16. Для реализации прямого обхода используется структура данных типа "последним вошел, первым вышел " (LIFO); для реализации обхода по уровням используется структура данных типа "первым вошел, первым вышел " (FIFO). Эти программы заслуживают внимательного изучения, поскольку они представляют существенно различающиеся подходы к организации оставшейся невыполненной работы. В частности, обход по уровням не соответствует рекурсивной реализации, связанной с рекурсивной структурой дерева.

Программа 5.15. Прямой обход (нерекурсивная реализация)

Эта нерекурсивная функция с использованием стека функционально эквивалентна ее рекурсивному аналогу - программе 5.14.

void traverse(link h, void visit(link))
  { STACK<link> s(max);
    s.push(h); 
    while (!s.empty())
      {
        visit(h = s.pop());
        if (h ->r != 0) s.push(h ->r);
        if (h ->l != 0) s.push(h ->l);
      }
  }
        

Программа 5.16. Обход по уровням

Замена структуры данных, лежащей в основе прямого обхода (см. программу 5.15), со стека на очередь дает обход по уровням.

void traverse(link h, void visit(link))
  { QUEUE<link> q(max);
    q.put(h);
    while (!q.empty())
      {
        visit(h = q.get());
        if (h ->l != 0) q.put(h ->l);
        if (h ->r != 0) q.put(h ->r);
      }
  }
        

Прямой обход, обратный обход и обход по уровням можно определить и для лесов. Чтобы определения были единообразными, представьте себе лес в виде дерева с воображаемым корнем. Тогда правило для прямого обхода формулируется следующим образом: "посетить корень, а затем каждое из поддеревьев "; а правило для обратного обхода - "посетить каждое из поддеревьев, а затем корень ". Правило для обхода по уровням то же, что и для бинарных деревьев. Непосредственные реализации этих методов - примитивные обобщения программ прямого обхода с использованием стека (программы 5.14 и 5.15) и программы обхода по уровням с использованием очереди (программа 5.16) для бинарных деревьев, которые мы только что рассмотрели. Конкретные реализации не приводятся, поскольку в разделе 5.8 будет рассмотрена более общая процедура.

Упражнения

5.79. Приведите порядок посещения узлов для прямого, поперечного, обратного и обхода по уровням для следующих бинарных деревьев:

5.80. Приведите содержимое очереди во время обхода по уровням (программа 5.16) дерева с рис 5.28 в стиле рис 5.27.

5.81. Покажите, что прямой обход леса эквивалентен прямому обходу соответствующего бинарного дерева (см. лемму 5.4), а обратный обход леса эквивалентен поперечному обходу бинарного дерева.

5.82. Приведите нерекурсивную реализацию поперечного обхода.

5.83. Приведите нерекурсивную реализацию обратного обхода.

5.84. Напишите программу, которая принимает на входе прямой и поперечный обходы бинарного дерева и генерирует обход дерева по уровням.

Рекурсивные алгоритмы для бинарных деревьев

Алгоритмы обхода дерева, рассмотренные в разделе 5.6, наглядно демонстрируют необходимость изучения рекурсивных алгоритмов для бинарных деревьев, что обусловлено рекурсивной структурой этих деревьев. Для решения многих задач можно непосредственно применять рекурсивные алгоритмы вида "разделяй и властвуй ", которые, по сути, обобщают алгоритмы обхода деревьев. Обработка дерева сводится к обработке корневого узла и (рекурсивно) его поддеревьев, и вычисление можно выполнять перед, между или после рекурсивных вызовов (или же использовать все три метода).

Часто требуется определить различные структурные параметры дерева, имея только ссылку на него. Например, программа 5.17 содержит рекурсивные функции для вычисления количества узлов и высоты заданного дерева. Эти функции написаны непосредственно исходя из определения 5.6. Ни одна из этих функций не зависит от порядка обработки рекурсивных вызовов: они обрабатывают все узлы дерева и возвращают одинаковый результат для любого порядка рекурсивных вызовов. Не все параметры дерева вычисляются так легко: например, программа для эффективного вычисления длины внутреннего пути бинарного дерева более сложна (см. упражнения 5.88 - 5.90).

Еще одна функция, которая бывает нужна при создании программ, обрабатывающих деревья - функция, которая выводит структуру дерева или вычерчивает его. Например, программа 5.18 представляет собой рекурсивную процедуру, выводящую дерево в формате, приведенном на рис 5.29. Эту же базовую рекурсивную схему можно использовать для вычерчивания более сложных представлений деревьев, подобных приведенным на рисунках в этой книге (см. упражнение 5.85).

(рис 5.29) Вывод дерева (при поперечном и прямом обходе)

Левая часть получена в результате работы программы 5.18 с деревом, приведенным на рис 5.26. В ней приведена структура дерева, подобная графическому представлению, которое используется в данной книге, но повернутая на 90 градусов. Правая часть получена в результате выполнения этой же программы, где оператор вывода перемещен в начало программы; здесь показана структура дерева в привычном схематическом формате.

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

Программа 5.17. Вычисление параметров дерева

Для выяснения базовых структурных свойств дерева можно использовать такие рекурсивные процедуры.

int count(link h)
  {
    if (h == 0) return 0;
    return count(h ->l) + count(h ->r) + 1;
  }
int height(link h)
  {
    if (h == 0) return  -1;
    int u = height(h ->l), v = height(h ->r);
    if (u > v) return u+1; else return v+1;
  }
        

Программа 5.18. Функция быстрого вывода дерева

Эта рекурсивная программа отслеживает высоту дерева и использует эту информацию для подсчета отступов при выводе представления, которое можно использовать для отладки программ обработки деревьев (см. рис 5.29). Здесь предполагается, что элементы в узлах имеют тип Item, для которого определена перегруженная операция <<.

void printnode(Item x, int h)
  { for (int i = 0; i < h; i++) cout << " ";
    cout << x << endl;
  }
void show(link t, int h)
  {
    if (t == 0) { printnode('*', h); return; }
    show(t ->r, h+1);
    printnode(t ->item, h);
    show(t ->l, h+1);
  }
        

Такой формат применяется для вывода генеалогического дерева, списка файлов в древовидной файловой структуре или при создании структуры печатного документа. Например, прямой обход дерева, приведенного на рис 5.19, выводит оглавление этой книги.

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

Программа 5.19 - рекурсивная программа, которая строит турнир из элементов массива. Будучи расширенной версией программы 5.6, она использует стратегию "разделяй и властвуй ": чтобы построить турнир для единственного элемента, программа создает лист, содержащий этот элемент, и возвращает этот элемент. Чтобы построить турнир для N > 1 элементов, программа делит все множество элементов пополам, строит турнир для каждой половины и создает новый узел со ссылками на эти два турнира и с элементом, который является копией большего элемента в корнях обоих турниров.

На .

Вообще -то реализации с использованием деревьев для нескольких из АТД обобщенных очередей (рассмотренных в разделе 4.6 ) являются основной темой обсуждения в значительной части этой книги. В частности, многие из алгоритмов, приведенных в главах 12 - 15, основываются на деревьях бинарного поиска (binary search tree) - это деревья, соответствующие бинарному поиску, аналогично тому, как структура на рис 5.30 соответствует рекурсивному алгоритму отыскания максимума (см. рис 5.6). Сложность реализации и использования таких структур заключается в обеспечении их эффективности после выполнения большого числа операций вставить, удалить и т.п.

Вторым примером программы создания бинарного дерева служит измененная версия программы вычисления префиксного выражения из раздела 5.1 (программа 5.4), которая не просто вычисляет префиксное выражение, а создает представляющее его дерево (см. ррис 5.31). В программе 5.20 используется та же рекурсивная схема, что и в программе 5.4, но рекурсивная функция возвращает не значение, а ссылку на дерево.

Программа создает новый узел дерева для каждого символа в выражении: узлы, которые соответствуют операциям, содержат ссылки на свои операнды, а листовые узлы содержат переменные (или константы), которые являются входными данными выражения.

Программа 5.19. Построение турнира

Данная рекурсивная функция делит массив a[1], ..., a[r] на две части a[1], ..., a[m] и a[m+1], ..., a[r], строит (рекурсивно) турниры для этих двух частей и создает турнир для всего массива, установив ссылки в новом узле на рекурсивно построенные турниры и поместив в него копию большего элемента из корней двух рекурсивно построенных турниров.

struct node
  { Item item; node *l, *r;
    node(Item x)
      { item = x; l = 0; r = 0; }
  };
typedef node* link;
link max(Item a[], int l, int r)
  { int m = (l+r)/2;
    link x = new node(a[m]);
    if (l == r) return x;
    x ->l = max(a, l, m);
    x ->r = max(a, m+1, r);
    Item u = x ->l ->item, v = x ->r ->item;
    if (u > v) x ->item = u; else x ->item = v;
    return x;
  }
        

(рис 5.30) Дерево для отыскания максимума (турнир)

На этом рисунке показана структура дерева, созданная программой 5.19 из входных данных A M P L E. Элементы данных находятся в листьях. Каждый внутренний узел содержит копию большего из элементов в двух дочерних узлах, так что по индукции наибольший элемент находится в корне.

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

В этом разделе было рассмотрено несколько примеров, демонстрирующих тезис о возможности создания и обработки связных древовидных структур с помощью рекурсивных программ. Чтобы этот подход стал эффективным, потребуется учесть производительность различных алгоритмов, альтернативные представления, нерекурсивные варианты и ряд других нюансов. Однако мы отложим более подробное изучение программ обработки деревьев до , поскольку в лекциях 7 - 11 деревья используются в основном в описательных целях. К явным реализациям деревьев мы вернемся в , поскольку они служат основой для многих алгоритмов, рассматриваемых в лекциях 12 - 15 .

Программа 5.20. Создание дерева синтаксического анализа

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

char *a; int i;
struct node
  { Item item; node *l, *r;
    node(Item x)
      { item = x; l = 0; r = 0; }
  };
typedef node* link;
link parse()
  { char t = a[i++];
    link x = new node(t);
    if ((t == '+') || (t == '*'))
      { x ->l = parse(); x ->r = parse(); }
    return x;
  }
        

(рис 5.31) Дерево синтаксического анализа

Это дерево создано программой 5.20 для префиксного выражения * + a * * b c + d e f. Оно представляет собой естественный способ представления выражения: каждый операнд размещается в листе (который показан здесь в качестве внешнего узла), а каждая операция должна выполняться с выражениями, которые представлены левым и правым поддеревьями узла, содержащего операцию.

Упражнения

5.85. Измените программу 5.18, чтобы она выводила PostScript -программу, которая вычерчивает дерево в формате как на рис 5.23, но без квадратиков, представляющих внешние узлы. Для вычерчивания линий используйте функции moveto и lineto, а для отрисовки узлов - пользовательскую операцию

/node {newpath moveto currentpoint 4 0 360 arc fill} def

После инициализации этого определения вызов node приводит к помещению черной точки с координатами, которые находятся в стеке (см. ).

5.86. Напишите программу, которая подсчитывает листья в бинарном дереве.

5.87. Напишите программу, которая подсчитывает количество узлов в бинарном дереве с одним внешним и одним внутренним дочерними узлами.

5.88. Напишите рекурсивную программу, которая вычисляет длину внутреннего пути бинарного дерева, используя определение 5.6.

5.89. Определите количество вызовов функций, выполненных программой при вычислении длины внутреннего пути бинарного дерева. Докажите ответ методом индукции.

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

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

Обход графа

В качестве заключительного примера в этой главе рассмотрим одну из наиболее важных рекурсивных программ: рекурсивный обход графа, или поиск в глубину (depth -first search). Этот метод систематического посещения всех узлов графа представляет собой непосредственное обобщение методов обхода деревьев, рассмотренных в разделе 5.6, и служит основой для многих базовых алгоритмов обработки графов (см. часть 7). Это простой рекурсивный алгоритм. Начиная с любого узла v, мы

посещаем v;

(рекурсивно) посещаем каждый (не посещенный) узел, связанный с v.

Если граф является связным, со временем будут посещены все узлы. Программа 5.21 является реализацией этой рекурсивной процедуры.

Программа 5.21. Поиск в глубину

Для посещения в графе всех узлов, связанных с узлом к, мы помечаем его как посещенный, а затем (рекурсивно) посещаем все не посещенные узлы в списке смежности узла к.

void traverse(int k, void visit(int))
  { visit(k); visited[k] = 1;
    for (link t = adj[k]; t != 0; t = t ->next)
      if (!visited[t ->v]) traverse(t ->v, visit);
  }
        

Например, предположим, что используется представление в виде списков связности, приведенное для графа на рис 3.15. На рис 5.32 приведена последовательность вызовов, выполненных при поиске в глубину в этом графе, а последовательность прохождения ребер графа показана в левой части рис 5.33. При прохождении каждого из ребер графа возможны два варианта: если ребро приводит к уже посещенному узлу, мы игнорируем его; если оно приводит к еще не посещенному узлу, мы проходим по нему с помощью рекурсивного вызова. Множество всех пройденных таким образом ребер образует остовное дерево графа.

(рис 5.32) Вызовы функции поиска в глубину

Эта последовательность вызовов функций реализует поиск в глубину для графа, приведенного на рис 3.15. Дерево, которое описывает структуру рекурсивных вызовов (вверху), называется деревом поиска в глубину.

Различие между поиском в глубину и общим обходом дерева (см. программу 5.14) состоит в том, что необходимо явно исключить посещение уже посещенных узлов. В дереве такие узлы не встречаются. Действительно, если граф является деревом, рекурсивный поиск в глубину, начинающийся с корня, эквивалентен прямому обходу.

Лемма 5.10. Время, необходимое для поиска в глубину в графе с V вершинами и E ребрами, пропорционально V + E, если используется представление графа в виде списков смежности.

В представлении в виде списков смежности каждому ребру графа соответствует один узел в списке, а каждой вершине графа соответствует один указатель на начало списка. Поиск в глубину использует каждый из них не более одного раза. $$$\blacksquare$$$

Поскольку время, необходимое для построения представления в виде списков смежности из последовательности ребер (см. программу 3.19), также пропорционально с линейным временем выполнения. Однако для очень больших графов решения вида объединение -поиск могут оказаться предпочтительнее, поскольку для представления всего графа нужен объем памяти, пропорциональный E, а для решений объединение -поиск - пропорциональный только V.

Как и в случае обхода дерева, можно определить метод обхода графа, при котором используется явный стек (см. рис 5.34). Можно представить себе абстрактный стек, содержащий двойные элементы: узел и указатель на список смежности для этого узла. Если вначале стек содержит начальный узел, а указатель указывает на первый элемент списка смежности для этого узла, алгоритм поиска в глубину эквивалентен входу в цикл, в котором сначала посещается узел из верхушки стека (если он еще не был посещен); потом сохраняется узел, указанный текущим указателем списка смежности; затем ссылка из списка смежности сдвигается на следующий узел (с выталкиванием элемента, если достигнут конец списка смежности); и, наконец, в стек заносится элемент для сохраненного узла со ссылкой на первый узел его списка смежности.

(рис 5.33) Поиск в глубину и поиск в ширину

При поиске в глубину (слева) перебираются все узлы, с возвратом к предшествующему узлу, когда все связи данного узла проверены. При поиске в ширину (справа) сначала перебираются все связи данного узла, а затем выполняется переход к следующему узлу.

Или же, как это было сделано для обхода дерева, можно создать стек, содержащий только ссылки на узлы. Если вначале стек содержит начальный узел, мы входим в цикл, в котором посещаем узел на верхушке стека (если он еще не был посещен), затем заносим в стек все узлы, смежные с этим узлом. На рис 5.34 видно, что для нашего примера графа оба метода эквивалентны поиску в глубину, причем эквивалентность сохраняется и в общем случае.

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

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

(рис 5.34) Динамика стека при поиске в глубину

Стек, обеспечивающий поиск в глубину, можно представить себе как содержащий элементы, каждый из которых состоит из узла и ссылки на список смежности для этого узла (показан узлом в кружке) (слева). Таким образом, обработка начинается с находящегося в стеке узла 0 со ссылкой на первый узел в его списке смежности - узел 7. Каждая строка отражает результат выталкивания из стека, занесения ссылки на следующий узел в списке посещенных узлов и занесения в стек элемента для не посещенных узлов. Этот процесс можно также представить себе в виде простого занесения в стек всех узлов, смежных с любым не посещенным узлом (справа).

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

Алгоритм, описанный в предыдущем абзаце, заслуживает внимания, поскольку вместо стека можно использовать любой АТД обобщенной очереди и все же посетить каждый из узлов графа (плюс сгенерировать развернутое дерево). Например, если вместо стека задействовать очередь, то получится поиск в ширину, который аналогичен обходу дерева по уровням. Программа 5.22 - реализация этого метода (при условии, что используется реализация очереди наподобие программы 4.12); пример этого алгоритма в действии показан на рис 5.35. В части 6 будет рассмотрено множество алгоритмов обработки графов, основанных на более сложных АТД обобщенных очередей.

И при поиске в ширину, и при поиске в глубину посещаются все узлы графа, но в совершенно различном порядке (см. рис 5.36). Поиск в ширину подобен армии разведчиков, разосланных по всей территории; поиск в глубину соответствует единственному разведчику, который проникает как можно дальше вглубь неизведанной территории, возвращаясь только в случае, если наталкивается на тупик. Это базовые методы решения задач, играющих существенную роль во многих областях компьютерных наук, а не только в поиске в графах.

Программа 5.22. Поиск в ширину

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

void traverse(int k, void visit(int))
  {
    QUEUE<int> q(V*V);
    q.put(k);
    while (!q.empty())
      if (visited[k = q.get()] == 0)
        {
          visit(k); visited[k] = 1;
          for (link t = adj[k]; t != 0; t = t ->next)
if (visited[t ->v] == 0) q.put(t ->v);
        }
  }
        

(рис 5.35) Динамика очереди при поиске в ширину

Обработка начинается с узла 0 в очереди, затем мы извлекаем узел 0, посещаем его и помещаем в очередь узлы 7 5 2 1 6 из его списка смежности, причем именно в этом порядке. Затем мы извлекаем узел 7, посещаем его и помещаем в очередь узлы из его списка смежности, и т.д. В случае запрета дублирования по правилу "игнорировать новый элемент " (справа) мы получаем такой же результат без лишних элементов в очереди.

(рис 5.36) Деревья обхода графов

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

А при поиске в ширину посещаются все узлы, связанные с данным, прежде чем двигаться дальше; поэтому некоторые узлы связаны с множеством других.

Упражнения

5.92. Построив диаграммы, соответствующие рис 5.33 (слева) и 5.34 (справа), покажите, как происходит посещение узлов при рекурсивном поиске в глубину в графе, построенном для последовательности ребер 0 -2, 1 -4, 2 -5, 3 -6, 0 -4, 6 -0 и 1 -3 (см. упражнение 3.70).

5.93. Построив диаграммы, соответствующие рис 5.33 (слева) и 5.34 (справа), покажите, как происходит посещение узлов при поиске в ширину (с использованием стека) в графе, построенном для последовательности ребер 0 -2, 1 -4, 2 -5, 3 -6, 0 -4, 6 -0 и 1 -3 (см. упражнение 3.70).

5.94. Построив диаграммы, соответствующие рис 5.33 (слева) и 5.35 (справа), покажите, как происходит посещение узлов при поиске в ширину (с использованием очереди) в графе, построенном для последовательности ребер 0 -2 , 1 -4 , 2 -5, 3 -6, 0 -4, 6 -0 и 1 -3 (см. упражнение 3.70).

5.95. Почему время выполнения, упоминаемое в лемме 5.10, пропорционально V + E, а не просто E ?

5.96. Построив диаграммы, соответствующие рис 5.33 (слева) и 5.35 (справа), покажите, как происходит посещение узлов при поиске в глубину (с использованием стека и правила "забыть старый элемент ") в графе, приведенном на рис 3.15.

5.97. Построив диаграммы, соответствующие рис 5.33 (слева) и 5.35 (справа), покажите, как происходит посещение узлов при поиске в глубину (с использованием стека и правила "игнорировать новый элемент ") в графе, приведенном на рис 3.15.

5.98. Реализуйте поиск в глубину с использованием стека для графов, которые представлены списками смежности.

5.99. Реализуйте рекурсивный поиск в глубину для графов, которые представлены списками смежности.

Перспективы

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

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

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

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

Несмотря на центральную роль в разработке алгоритмов, рекурсия - вовсе не панацея на все случаи жизни. Как было показано при изучении алгоритмов обхода деревьев и графов, алгоритмы с использованием стека (которые рекурсивны по своей природе) - не единственная возможность при необходимости управлять сразу несколькими вычислительными задачами. Эффективная техника разработки алгоритмов для решения многих задач заключается в использовании реализаций обобщенных очередей, отличающихся от стеков; такие очереди позволяют выбирать следующую задачу в соответствии с каким -либо более субъективным критерием, нежели простой выбор самой последней. Структуры данных и алгоритмы, которые эффективно поддерживают такие операции - основная тема , а со многими примерами их применения мы встретимся во время изучения алгоритмов обработки графов в части 7.

Ссылки для части II

Существует множество учебников для начинающих, посвященных структурам данных. Например, в книге Стендиша (Standish) темы связных структур, абстракций данных, стеков и очередей, распределения памяти и создания программ освещаются более подробно, чем здесь. Конечно, классические книги Кернигана и Ритчи (Kernighan -Ritchie) и Страуструпа (Stroustrup) - бесценные источники подробной информации по реализациям на С и С++. Книги Мейерса (Meyers) также содержат полезную информацию о реализациях на C++.

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

Парадигма "клиент -интерфейс -реализация " подробно и с множеством примеров описывается в книге Хэнсона (Hanson). Эта книга - замечательный справочник для тех программистов, которые намерены писать надежный и переносимый код для больших систем.

Книги Кнута (Knuth), в особенности 1 -й и 3 -й тома, остаются авторитетным источником информации по свойствам элементарных структур данных. Книги Баеcа -Ятеса (Baeza -Yates) и Гонне (Gonnet) содержат более свежую информацию, подкрепленную внушительным библиографическим перечнем. Книга Седжвика и Флажоле (Sedgewick and Flajolet) подробно освещает математические свойства деревьев.

1. Adobe Systems Incorporated, PostScript Language Reference Manual, second edition, Addison -Wesley, Reading, MA, 1990.

2. R. Baeza -Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison -Wesley, Reading, MA, 1984.

3. D. R. Hanson, C Interfaces and Implementations: Techniques for Creating Reusable Software, Addison -Wesley, 1997.

4. Брайан У. Керниган, Деннис М. Ритчи, Язык программирования C (Си), 2 -е издание, ИД "Вильямс", 2008 г.

5. Д.Э. Кнут, Искусство программирования, том 1: Основные алгоритмы, 3 -е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 2: Получисленные алгоритмы, 3 -е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2 -е издание, ИД "Вильямс", 2008 г.

6. S. Meyers, Effective C++, second edition, Addison -Wesley, Reading, MA, 1996.

7. S. Meyers, More Effective C++, Addison -Wesley, Reading, MA, 1996.

8. R. Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms, Addison -Wesley, Reading, MA, 1996.

9. T. A. Standish, Data Structures, Algorithms, and Software Principles in C, Addison -Wesley, 1995.

10. B. Stroustrup, The C++ Programming Language, third edition, Addison -Wesley, Reading MA, 1997.