Эти рекурсивные функции для выполнения простых задач обработки списков легко выразить, но они могут быть бесполезны для очень больших списков, поскольку глубина рекурсии может быть пропорциональна длине списка.
Первая функция count подсчитывает количество узлов в списке. Вторая, traverse, вызывает функцию visit для каждого узла списка, с начала до конца. Обе функции легко реализуются с помощью цикла for или while. Третья функция traverseR не имеет простого итеративного аналога. Она вызывает функцию visit для каждого узла списка, но в обратном порядке.
Четвертая функция remove удаляет из списка все узлы с заданным значением элемента. Основа реализации этой функции —изменение связи х = x-> next в узле, предшествующем удаляемому, что возможно благодаря использованию параметра ссылки.
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 (links x, Item v)
{
while (x!= 0 && x->item == v)
{ link t = x; x = x->next; delete t; }
if (x!= 0) remove (x->next, v);
}
Некоторые среды программирования автоматически выявляют и исключают листовую (оконечную) рекурсию (tail recursion); когда последним действием функции является рекурсивный вызов, увеличение глубины рекурсии вовсе не обязательно. Это усовершенствование эффективно преобразовало бы функции подсчета, обхода и удаления, используемые в программе 5 в циклы, но оно не применимо к функции обхода в обратном направлении.
Деревья
Деревья — это математические абстракции, играющие главную роль при разработке и анализе алгоритмов, поскольку[3]:
1. Мы используем деревья для описания динамических свойств алгоритмов;
2. Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев.
Мы часто встречаемся с деревьями в повседневной жизни — это основное понятие очень хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Еще один пример — организация спортивных турниров; среди прочих, в исследовании этого применения принял участие и Льюис Кэрролл (Lewis Carroll). В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение
отличается иерархическим разделением. Четвертым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков. Типичный пример дерева, в данном случае описывающего структуру этой книги, показан на рис. 10.
Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.
Существует множество различных типов деревьев, и важно понимать различие между абстракцией и конкретным представлением, с которым выполняется работа для данного приложения. Соответственно, мы подробно рассмотрим различные типы деревьев и их представления. Рассмотрение начнется с определения деревьев как абстрактных объектов и с ознакомления с большинством основных связанных с ними терминов. Мы неформально рассмотрим различные типы деревьев, которые следует рассматривать в порядке сужения самого этого понятия:
1. Деревья
2.Деревья с корнем
3.Упорядоченные деревья
4.М-арные и бинарные деревья
После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения. На рис. 11 приведена иллюстрация многих из этих базовых концепций, которые будут сначала рассматриваться, а
затем и определяться.
Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами. Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева — существование только одно
пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest).
Рис.10. Дерево
Рис. 11. Типы деревьев
Дерево с корнем (единственным, rooted) — это дерево, в котором один узел назначен корнем (root) дерева. В области компьютеров термин дерево обычно применяется к деревьям с корнем, а термин свободное дерево (free tree) — к более общим структурам, описанным в предыдущем абзаце. В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов.
Существует только один путь между корнем и каждым из других узлов дерева. Данное определение никак не определяет направление ребер; обычно считается, что все ребра указывают от корня или к корню, в зависимости от приложения. Обычно деревья с корнем рисуются с корнем, расположенным в верхней части (хотя на первый взгляд это соглашение кажется неестественным), и говорят, что узел у располагается под узлом х (а х располагается над у), если jc находится на пути от у к корню (т.е., у находится под х, как нарисовано на странице, и соединяется с х путем, который не проходит через корень). Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом (parent); узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами (children). Иногда аналогия с генеалогическими деревьями расширяется еще больше
и тогда говорят об узлах-предках (grand parent) или родственных (sibling) узлах данного узла.
Узлы, не имеющие дочерних узлов, называются листьями (leaves) или терминальными (оконечными, terminal) узлами. Для соответствия с последним применением узлы, имеющие хотя бы один дочерний узел, иногда называются нетерминальными (nonterminal) узлами.
В определенных приложениях способ упорядочения дочерних узлов каждого узла имеет значение; в других это не важно. Упорядоченное (ordered) дерево — это дерево с корнем, в котором определен порядок следования дочерних узлов каждого узла. Упорядоченные деревья — естественное представление: например, при рисовании дерева дочерние узлы размещаются в определенном порядке. Действительно, многие другие конкретные представления имеют аналогично предполагаемый порядок; пример, обычно это различие имеет значение при рассмотрении представления деревьев в компьютере.
Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда внешние узлы могут действовать в качестве фиктивных, на которые ссылаются узлы, не имеющие указанного количества дочерних узлов. В частности, простейшим типом Af-арного дерева является бинарное дерево. Бинарное дерево (binary tree) — это упорядоченное дерево, состоящее из узлов двух типов: внешних узлов без дочерних узлов и внутренних узлов, каждый из которых имеет ровно два дочерних узла. Поскольку два дочерних узла каждого внутреннего узла упорядочены, говорят о левом дочернем
узле (left child) и правом дочернем узле (right child) внутренних узлов. Каждый внутренний узел должен иметь и левый, и правый дочерние узлы, хотя один из них или оба могут быть внешними узлами. Лист в М-арном дереве — это внутренний узел, все дочерние узлы которого являются внешними.
Все это общая терминология. Далее рассматриваются формальные определения, представления и приложения, в порядке расширения понятий:
1. Бинарные и М-арные деревья
2.Упорядоченные деревья
3.Деревья с корнем
4.Вободные деревья
Начав с наиболее характерной абстрактной структуры, мы должны быть в состоянии подробно рассмотреть конкретные представления, как станет понятно из дальнейшего изложения.
Определение 1. Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.
Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие. При работе с компьютерными представлениями мы работаем всего лишь с одной конкретной реализацией этой абстракции. Эта ситуация не отличается от представления действительных чисел значениями типа float, целых чисел значениями типа int и т.д. Когда мы рисуем дерево с узлом в корне, связанным ребрами с левым поддеревом, расположенным слева, и с правым поддеревом, расположенным справа, то выбираем удобное конкретное представление. Существует множество различных способов представления бинарных деревьев, которые поначалу кажутся удивительными, но вполне отражают сущность, как и можно было ожидать, учитывая абстрактный характер определения.
Чаще всего применяется следующее конкретное представление при реализации программ, использующих и манипулирующих бинарными деревьями, — структура с двумя связями (правой и левой) для внутренних узлов (см. рис. 12). Эти структуры аналогичны связным спискам, но они имеют по две связи для каждого узла, а не по одной. Нулевые связи соответствуют внешним узлам. В частности, мы добавили связь к стандартному представлению связного списка, следу- следующим образом:
struct node { Item item; node *1, *r; }
typedef node *link;
что представляет собой всего лишь код C++ для определения 1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями. Так, например, мы реализуем абстрактную операцию перехода к левому поддереву с помощью ссылки на указатель типа х = х->1.
Это стандартное представление позволяет построить эффективную реализацию операций, которые вызываются для перемещения по дереву вниз от корня, но не для перемещения по дереву вверх от дочернего узла к его родительскому узлу. Для алгоритмов, требующих использования таких операций, можно добавить третью связь для каждого узла, направленную к его родительскому узлу. Эта альтернатива аналогична двухсвязным спискам. Как и в случае со связными списками в определенных ситуациях узлы дерева хранятся в массиве, а в качестве связей используются индексы, а не указатели. Для определенных специальных алгоритмов используются другие представления бинарных деревьев.
Анализируя связные списки, мы начали рассмотрение с элементарных операций вставки и удаления узлов. При использовании стандартного представления бинарных деревьев такие операции необязательно являются элементарными из-за наличия второй связи. Если нужно удалить узел из бинарного дерева, приходится решать принципиальную проблему наличия двух дочерних узлов и только одного родительского, с которыми нужно работать после удаления узла. Существуют три естественных операции, для которых подобное осложнение не возникает: вставка нового узла в нижней части дерева (замена нулевой связи связью с новым узлом), удаление листа (замена связи с ним нулевой связью) и объединение двух деревьев посредством создания нового корня, левая связь которого указывает на одно дерево, а правая — на другое. Эти операции интенсивно используются при манипулировании бинарными деревьями.
Опредление 2. М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-арными деревьями.
Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей. Например, 3-арные (или троичные) деревья, в которых используются структуры с тремя именованными связями (левой, средней и правой), каждая из которых имеет специальное значение для связанных с ними алгоритмов. В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти.
Определение 3. Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется бором.
Различие между упорядоченными деревьями и М-арными деревьями состоит в том, что узлы в упорядоченных деревьях могут иметь любое количество дочерних узлов, в то время как узлы в М-арных деревьях должны иметь точно М дочерних узлов. Иногда в контекстах, в которых требуется различать упорядоченные и М-арные деревья, мы используем термин главное дерево (general tree).
Поскольку каждый узел в упорядоченном дереве может иметь любое количество связей, представляется естественным рассматривать его с использованием связного списка, а не массива, для хранения связей с дочерними узлами. Пример такого представления приведен на рис. 13. Из этого примера видно, что тогда каждый узел содержит две связи: одну для связного списка, соединяющего его с родственными узлами, и вторую для связного списка его дочерних узлов.
Лемма 1. Существует однозначное соответствие между бинарными деревьями и упорядоченными борами.
Это соответствие показано на рис. 13. Любой бор можно представить в виде бинарного дерева, сделав левую связь каждого узла указывающей на его левый дочерний узел, а правую связь каждого узла — указывающей на родственный узел, расположенный справа.
Рис.12. Представление бинарного дерева
Определение 4. Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.)
Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел. Например, основные деревья, полученные в результате работы алгоритмов связности, обладают этим свойством. Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphs).
Определение 5. Граф — это набор узлов с набором ребер, которые соединяют пары отдельных узлов (причем любую пару узлов соединяет только одно ребро).
Рис.13. Представление дерева
Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д. Последовательность ребер, ведущих от одного узла до другого, когда ни один узел не посещается дважды, называется простым путем. Граф является связным (connected), если существует простой путь, связывающий любую пару узлов. Простой путь, у которого первый и последний узел совпадают, называется циклом (cycle).
Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому из следующих четырех условий:
1. Граф имеет N — 1 ребер и ни одного цикла.
2. Граф имеет N— 1 ребер и является связным.
3. Только один простой путь соединяет каждую пару вершин в графе.
4. Граф является связным, но перестает быть таковым при удалении любого ребра.
Любое из этих условий — необходимое и достаточное условие для выполнения остальных трех. Формально, одно из них должно было бы служить определением свободного дерева; неформально, они все вместе служат определением.
Мы представляем свободное дерево в виде коллекции ребер. Если представлять свободное дерево неупорядоченным, упорядоченным или даже бинарным деревом, придется признать, что в общем случае существует множество различных способов представления каждого свободного дерева.
Абстракция дерева используется часто, и рассмотренные в этом разделе различия важны, поскольку знание различных абстракций деревьев — существенная составляющая определения эффективного алгоритма и соответствующих структур данных для решения данной задачи. Часто приходится работать непосредственно с конкретными представлениями деревьев без учета конкретной абстракции, но в то же время часто имеет смысл поработать с соответствующей абстракцией дерева, а затем рассмотреть различные конкретные представления.
Обход дерева
Прежде чем рассматривать алгоритмы, конструирующие бинарные деревья и деревья, рассмотрим алгоритмы для реализации наиболее общей функции обработки деревьев — обхода дерева; при наличии указателя на дерево требуется систематически обработать все узлы в дереве. В связном списке переход от одного узла к другому выполняется за счет отслеживания единственной связи; однако, в случае деревьев приходится принимать решения, поскольку может существовать несколько связей, по которым можно следовать[3].
Начнем рассмотрение с процесса для бинарных деревьев. В случае со связными списками имелись две основные возможности (см. программу 5): обработать узел, а затем следовать связи (в этом случае узлы посещались бы по порядку), или следовать связи, а затем обработать узел (в этом случае узлы посещались бы в обратном порядке). При работе с бинарными деревьями существуют две связи и, следовательно, три основных порядка возможного посещения узлов:
1. Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья
2. Поперечный обход (слева направо), при котором мы посещаем левое поддерево, затем узел, а затем правое поддерево
3. Обратный обход (снизу-вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.
Эти методы можно легко реализовать с помощью рекурсивной программы, как показано в программе 6, которая является непосредственным обобщением программы 5 обхода связного списка. Для реализации обходов в других порядках достаточно соответствующим образом переставить вызовы функций в программе 6. Порядок посещения узлов в примере дерева при использовании каждого из порядков обхода показан на рис. 15. На рис. 14 приведена последовательность вызовов функций, которые выполняются при вызове программы 6 применительно к примеру
дерева из рис. 15.