8.1. Деревья и рекурсивные алгоритмы

8. Нелинейные структуры данных. Деревья и графы

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

Определение дерева. Дерево и рекурсия

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

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

void ScanTree(текущая вершина) {
  if (текущая вершина == NULL) return;

  for (перебор потомков) ScanTree(i-ый потомок)
}

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

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

Способы представления деревьев

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

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

![рис. 81.1. Дерево в массиве с индексами предков]./assets/081-01.png)

//------------------------------------------------------91-01.cpp
struct mtree {
  char *s;
  int parent;
};

mtree A1[] = {
  {"aa",-1}, {"bb",0}, {"cc",1}, {"dd",0}, {"ee",8}, {"ff",1}, {"gg",3}, {"hh",5}, {"ii",3}, {"jj",7}, {"kk",7}
}; 

void scan_m(mtree A[], int n, int k, int level) { // k – индекс предка
  printf("l=%d node=%d s=%s\n",level,k,A[k].s);
  
  for (int i = 0; i < n; i++)  // Цикл выбора потомков вершины
    if (A[i].parent==k) scan_m(A,n,i,level+1);
} 

void main() { scan_m(A1,11,0,0); }

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

Представление дерева в массиве с вычисляемыми адресами потомков. Попробуем поставить вопрос нестандартно: если не искать, как было сделано выше, потомков, то, может быть, их адреса (или индексы) можно вычислить? Для некоторого вида деревьев, как например, с двумя потомками, принять способ размещения, в котором адреса (индексы) потомков вычисляются через адрес (индекс) предка. Если предок имеет индекс n, то два его потомка - 2n и 2n+1 соответственно. Корневая вершина имеет индекс 1. Отсутствующие потомки должны обозначаться специальным значением, например, -1.

![рис. 81.2. Дерево в массиве с вычислением адресов потомков]./assets/081-02.png)

//------------------------------------------------------91-01.cpp

void scan_2(int A[], int n, int k,int level){   // k – индекс текущей вершины

            if (k>=n) return;

            if (A[k]==-1) return;

            printf("l=%d node=%d val=%d\n",level,k,A[k]);

            scan_2(A,n,2*k,level+1);

            scan_2(A,n,2*k+1,level+1);

}

//              0 1   2 3  4   5 6 7  8  9

int A2[]={-1,2,10,3,15,-1,4,8,-1,17};

 

void main(){ scan_2(A2,10,1,0);  }

Получается быстро, а главное, без дополнительной информации, индекс массива однозначно определяет положение вершины. Но за это приходится расплачиваться. Каждый следующий уровень требует удвоения размерности массива, вне зависимости от того, сколько вершин этого уровня используются. Поэтому основное требование – сбалансированность. Если есть хотя бы одна ветвь, сильно отличающаяся по длине, то эффективность использования памяти резко снижается. Если же дерево вырождается в список, то размерность массива растет экспоненциально W=2N.

Представление дерева в виде ветвящегося списка. Наиболее близка «по духу» к дереву списковая структура, однако цепочка элементов в данном случае является не линейной, а разветвляющейся.

![рис. 81.3. Дерево на основе ветвящегося списка]./assets/081-03.png);

Каждая вершина содержит два указателя – на «старшего сына» – заголовок списка следующего уровня, и на «следующего брата» - ссылка в списке вершин текущего уровня.


//------------------------------------------------------81-01.cpp

// Представление дерева в виде разветвляющегося списка

struct ltree{

            char *s;

            ltree *son,*bro;   // Указатели на старшего сына

            };                                                          // и младшего брата

 

ltree      A={"aa",NULL,NULL},                 // Последняя в списке

            B={"bb",NULL,&A},

            C={"cc",NULL,&B},                    // Список потомков - концевых вершин A,B,C                D={"dd",NULL,NULL},

            E={"ee",&C,NULL},

            F={"ff",&D,&E},                          // Список потомков G - вершин F,E

            G={"gg",&F,NULL},

            *ph = &G;

 

void scan_l(ltree *p, int level){

            if (p==NULL) return;

            printf("l=%d val=%s\n",level,p->s);

            for (ltree *q=p->son;q!=NULL;q=q->bro)

                        scan_l(q,level+1);

                        }

void main(){ scan_l(ph,0); }

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

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

#define N 4

//------------------------------------------------------81-01.cpp

struct tree{

      char *s;

      int n;                              // Количество потомков в МУ

      tree *ch[N];

      };

 

tree  H1={"aa",0},           

            B1={"bb",0},

            C1={"cc",0},

            D1={"dd",0},

            E1={"ee",3,&C1,&B1,&H1},

            F1={"ff",0},           

            G1={"gg",3,&F1,&E1,&D1},

            *ph1 = &G1;

 

 

void scan(tree *p, int level){

      if (p==NULL) return;

      printf("l=%d val=%s\n",level,p->s);

      for (int i=0; i<p->n; i++)

            scan(p->ch[i],level+1);

            }

Эффективность алгоритмов, работающих с деревьями

Можно провести аналогии между парой «деревья - рекурсивные алгоритмы» и «пространство-время». При работе рекурсивной программы происходит развертке дерева вызовов функции во времени, а дерево, как структура данных, выглядит как отображенный в памяти результат выполнения рекурсивного алгоритма. Именно поэтому к деревьям применимы выводы относительно эффективности рекурсивных алгоритмов:

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

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

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

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

Трудоемкость алгоритмов на деревьях. Хотя деревья являются и топологически сложными структурами данных, оценить пределы и условия их эффективности довольно легко. Прежде всего, введем такую характеристику дерева, как сбалансированность. Сбалансированность характеризует разброс длин ветвей дерева. Более точно, речь идет о расстояниях от корневой вершины до вершины со свободной ветвью. Дерево называется сбалансированным, если длина максимальной и минимальной ветвей отличается не более чем на 1. Для такого дерева характерна экспоненциальная (или обратная, логарифмическая) зависимость между длиной ветви и количеством вершин в дереве:

N = 1 + m + m2 + m3 + … + mL < mL , L < logmN

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

Далее, все алгоритмы, основанные на однократном, полном рекурсивном обходе, будут иметь линейную трудоемкость T=N. Их усовершенствование может состоять только в ограничении «глубины погружения», если на это есть достаточные основания. Другое дело, алгоритмы, основанные на ветвлении. В каждой вершины они выбирают только одного из возможных потомков. Такие алгоритмы называют жадными (см. «8.7. Эффективность рекурсивных алгоритмов»). Сразу же можно увидеть, что их трудоемкость равна длине выбранной ими ветви дерева. Для сбалансированного дерева зависимость будет логарифмической

T = L < logmN,

для вырожденного в список дерева – линейной. Здесь возникают две проблемы. Во-первых, поддержка сбалансированности дерева. Для нее имеется два решения:

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

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

Вторая проблема упирается в основания, которые имеет алгоритм для однозначного выбора единственного потомка в каждой вершине (художественная аналогия - «рыцарь на распутье»). Здесь опять же возможны два подхода:

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