• Название:

    Деревья и их обход

  • Размер: 0.08 Мб
  • Формат: DOC
  • или



Деревья и их обход

Деревья – это математические абстракции, играющие огромную роль при разработке и анализе алгоритмов, поскольку
Мы используем деревья для описания динамических свойств алгоритмов;
Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев.
Мы часто встречаемся с деревьями в повседневной жизни – это основное понятие хорошо знакомо.
Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения.
Ещё один пример – организация спортивных турниров; среди прочих, в исследовании этого применения принял участие Льюис Кэрролл.
В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа “разделяй и властвуй”. Четвёртым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков.
Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем.
Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов.
Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.
Существует множество различных типов деревьев, и важно понимать различиемежду абстракцией и конкретным представлением, с которым выполняется работадля данного приложения.
Соответственно, мы подробно рассмотрим различные типыдеревьев и их представления.
Рассмотрение начнется с определения деревьев как абстрактных объектов и с ознакомления с большинством основных связанных с нимитерминов.
Мы неформально рассмотрим различные типы деревьев, которые следует рассматривать в порядке сужения самого этого понятия:
• Деревья
• Деревья с корнем
• Упорядоченные деревья
• М-арные и бинарные деревья
После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения.
Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям.
Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами.
Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева.
Определяющее свойство дерева — существование только одного пути, соединяющего любые два узла.
Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево.
Несвязанный набор деревьев называется бором (forest).
Дерево с корнем (единственным,rooted) — это дерево, в котором один узел назначен корнем (root) дерева.
В области компьютеров термин дерево обычно применяетсяк деревьям с корнем, а термин свободное дерево (free tree) — к более общим структурам, описанным в предыдущем абзаце.
В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов.
Существует только один путь между корнем и каждым из других узлов дерева.
Данное определение никак не определяет направление ребер; обычно считается, чтовсе ребра указывают от корня или к корню, в зависимости от приложения.
Обычнодеревья с корнем рисуются с корнем, расположенным в верхней части (хотя на первый взгляд это соглашение кажется неестественным), и говорят, что узел у располагается под узлом x а x располагается над y), если x находится на пути от y к корню (т.е., у находится под х и соединяется с х путем, который не проходит через корень).
Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом (parent), узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами (children).
Иногда аналогия с генеалогическими деревьями расширяется еще больше, и тогда говорят об узлах-предках (grand parent) или родственных (sibling) узлах данного узла.
Узлы, не имеющие дочерних узлов, называются листьями (leaves) или терминальными (оконечными, terminal) узлами.
Для соответствия с последним применением узлы, имеющие хотя бы один дочерний узел, иногда называются нетерминальными (nonterminal) узлами.
В этой главе мы уже встречались с примером утилиты, различающей эти типы узлов.
В деревьях, которые использовались для представления структуры вызовов рекурсивных алгоритмов, нетерминальные узлы (окружности) представляют вызовы функций с рекурсивными вызовами, а терминальные узлы (квадраты) представляют вызовы функций без рекурсивных вызовов.
В определенных приложениях способ упорядочения дочерних узлов каждого узлаимеет значение; в других это не важно.
Упорядоченное (ordered) дерево — это деревос корнем, в котором определен порядок следования дочерних узлов каждого узла.
Упорядоченные деревья — естественное представление: например, при рисовании дерева дочерние узлы размещаются в определенном порядке.
Действительно, многиедругие конкретные представления имеют аналогично предполагаемый порядок; например, обычно это различие имеет значение при рассмотрении представления деревьев в компьютере.
Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево.
В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов.
Тогдавнешние узлы могут действовать в качестве фиктивных, на которые ссылаются узлы,не имеющие указанного количества дочерних узлов.
В частности, простейшим типом М-арного дерева является бинарное дерево.
Бинарное дерево (binary tree) ~ это упорядоченное дерево, состоящее из узлов двух типов: внешних узлов без дочерних узлови внутренних узлов, каждый из которых имеет ровно два дочерних узла.
Посколькудва дочерних узла каждого внутреннего узла упорядочены, говорят о левом дочернемузле (left child) и правом дочернем узле (right child) внутренних узлов.
Каждый внутренний узел должен иметь и левый, и правый дочерние узлы, хотя один из них или обамогут быть внешними узлами.
Лист в М-арном дереве — это внутренний узел, вседочерние узлы которого являются внешними.
Все это общая терминология.
Далее рассматриваются формальные определения,представления и приложения, в порядке расширения понятий;
• бинарные и M-арные деревья
• упорядоченные деревья
• деревья с корнем
• свободные деревья
Начав с наиболее характерной абстрактной структуры, мы должны быть в состоянии подробно рассмотреть конкретные представления, как станет понятно из дальнейшего изложения.
Определение 5.1 Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.
Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие.
При работе с компьютерными представлениями мы работаемвсего лишь с одной конкретной реализацией этой абстракции.
Эта ситуация не отличается от представления действительных чисел значениями типа float, целых чиселзначениями типа int и т.д.
Когда мы рисуем дерево с узлом в корне, связанным ребрами с левым поддеревом, расположенным слева, и с правым поддеревом, расположенным справа, то выбираем удобное конкретное представление.
Существует множество различных способов представления бинарных деревьев, которые поначалу кажутся удивительными, но вполне отражают сущность, как и можно было ожидать, учитывая абстрактный характер определения.
Чаще всего применяется следующее конкретное представление при реализации программ, использующих и манипулирующих бинарными деревьями, — структура с двумя связями (правой и левой) для внутренних узлов.
Эти структуры аналогичны связным спискам, но они имеют по две связи для каждого узла, а не по одной.
Нулевые связи соответствуют внешним узлам.
В частности, мы добавили связь к стандартному представлению связного списка, следующим образом:
struct node {Item item; node *l, *r;}
typedef node * link;
что представляет собой всего лишь код С++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями Так, например, мы реализуем абстрактную операцию перехода к левому поддереву cпомощью ссылки на указатель типа х = х->1.
Это стандартное представление позволяет построить эффективную реализациюопераций, которые вызываются для перемещения по дереву вниз от корня, но не дляперемещения по дереву вверх от дочернего узла к его родительскому узлу.
Для алгоритмов, требующих использования таких операций, можно добавить третью связь длякаждого узла, направленную к его родительскому узлу.
Эта альтернатива аналогична двухсвязным спискам.
Как и в случае со связными списками, в определенных ситуациях узлы дерева хранятся в массиве, а в качестве связей используются индексы, а не указатели.
Для определенных специальных алгоритмов используются другие представления бинарных деревьев.
Из-за наличия такого множества различных возможных представлений можно было бы разработать ADT (abstract data Туре) (абстрактный тип данных) бинарного дерева, инкапсулирующий важные операции, которые нужно выполнять, и разделяющий использование и реализацию этих операций.
В данной книге данный подход не используется, поскольку
• чаще всего мы используем представление с двумя связями;
• мы используем деревья для реализации АОТ более высокого уровня, и хотимсосредоточить внимание на этой теме;
• мы работаем с алгоритмами, эффективность которых зависит от конкретногопредставления, — это обстоятельство может быть упущено в АОТ.
По этим же причинам мы используем уже знакомые конкретные представлениямассивов и связных списков.
Представление бинарного дерева— один из фундаментальных инструментов, который теперь добавлен к этому краткому списку.
Анализируя связные списки, мы начали рассмотрение с элементарных операцийвставки и удаления узлов.
При использовании стандартного представления бинарных деревьев такие операции необязательно являются элементарными из-за наличия второй связи.
Если нужно удалить узел из бинарного дерева, приходится решать принципиальную проблему наличия двух дочерних узлов и только одного родительского, с которыми нужно работать после удаления узла.
Существуют три естественных операции, для которых подобное осложнение не возникает вставка нового узла в нижней части дерева (замена нулевой связи связью с новым узлом), удаление листа (замена связи с ним нулевой связью) и объединение двух деревьев посредством создания нового корня, левая связь которого указывает на одно дерево, а правая — на другое.
Эти операции интенсивно используются при манипулировании бинарными деревьями.
Определение 5.2 М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-ар-ными деревьями.
Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей.
В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти.
Определение 5.3 Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев.
Такая последовательность называется бором.
Различие между упорядоченными деревьями и М-арными деревьями состоит втом, что узлы в упорядоченных деревьях могут иметь любое количество дочернихузлов, в то время как узлы в М-арных деревьях должны иметь точно M дочерних узлов.
Иногда в контекстах, в которых требуется различать упорядоченные и М-арныедеревья, мы используем термин главное дерево (general tree).
Поскольку каждый узел в упорядоченном дереве может иметь любое количествосвязей, представляется естественным рассматривать его с использованием связногосписка, а не массива, для хранения связей с дочерними узлами.
Из этого примера видно, что тогда каждый узел содержит две связи: одну для связного списка, соединяющего его с родственными узлами, и вторую для связного списка его дочерних узлов.
Лемма 5.4 Существует однозначное соответствие между бинарными деревьями и упорядоченными борами.
Любой бор можно представить в виде бинарного дерева, сделав левую связь каждого узла указывающей на его левый дочерний узел, а правую связь каждого узла — указывающей на родственный узел, расположенный справа.
Определение 5.4 Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.)
Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево.
Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма дерева) трудно подается решению.
Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел.
Например, основные деревья, полученные в результате работы алгоритмов связности из главы 1, обладают этим свойством.
Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphsз).
Определение 5.5 Граф — это набор узлов с набором ребер, которые соединяют пары
отдельных узлов (причем любую пару узлов соединяет только одно ребро).
Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева.
На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов.
На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу.
Таким образом, бинарное дерево можно рассматривать в качестве представления дерева.
Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д.
Последовательность ребер, ведущих одного узла до другого, когда ни один узел не посещается дважды, называется простым путем.
Граф является связным (connected), если существует простой путь, связывающий любую пару узлов.
Простой путь, у которого первый и последний узел совпадают, называется циклом (сус1е).
Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому из следующих четырех условий:

- Граф имеет N - 1 ребер и ни одного цикла.- Граф имеет N-1 ребер и является связным.
- Только один простой путь соединяет каждую пару вершин в графе.- Граф является связным, но перестает быть таковым при удалении любого ребра. Любое из этих условий — необходимое и достаточное условие для выполнения остальных трех.
Формально, одно из них должно было бы служить определением свободного дерева', неформально, они все вместе служат определением.
Мы представляем свободное дерево в виде коллекции ребер.
Если представлять свободное дерево неупорядоченным, упорядоченным или даже бинарным деревом, придется признать, что в общем случае существует множество различных способов представления каждого свободного дерева.
Абстракция дерева используется часто, и рассмотренные в этом разделе различия важны, поскольку знание различных абстракций деревьев — существенная составляющая определения эффективного алгоритма и соответствующих структур данных для решения данной задачи.
Часто приходится работать непосредственно с конкретными представлениями деревьев без учета конкретной абстракции, но в то же время часто имеет смысл поработать с соответствующей абстракцией дерева, а затем рассмотреть различные конкретные представления.
В книге приведено множество примеров этого процесса.
Прежде чем вернуться к алгоритмам и представлениям, мы рассмотрим ряд основных математических свойств деревьев; эти свойства будут использоваться при разработке и анализе алгоритмов в виде деревьев.
Обход дерева
Когда количество внешних узлов является степенью 2, все внешние узлы в полном бинарном дереве располагаются на одном уровне.
В противном случаевнешние узлы располагаются в двух уровнях при размещении внутренних узлов слева от внешних узлов предпоследнего уровня.
Прежде чем рассматривать алгоритмы, конструирующие бинарные деревья и деревья, рассмотрим алгоритмы для реализации наиболее общей функции обработки деревьев — обхода дерева, при наличии указателя на дерево требуется систематически обработать все узлы в дереве.
В связном списке переход от одного узла к другому выполняется за счет отслеживания единственной связи; однако, в случае деревьев приходится принимать решения, поскольку может существовать несколько связей, по которым можно следовать.
Начнем рассмотрение с процесса для бинарных деревьев.
В случае со связными списками имелись две основные возможности (см. программу 5.5): обработать узел, а затем следовать связи (в этом случае узлы посещались бы по порядку), или следовать связи, а затем обработать узел (в этом случае узлы посещались бы в обратном порядке).
При работе с бинарными деревьями существуют две связи и, следовательно, три основных порядка возможного посещения узлов:
• Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья
• Поперечный обход (слева направо), при котором мы посещаем левое поддерево,затем узел, а затем правое поддерево
• Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.
Эти методы можно легко реализовать с помощью рекурсивной программы, какпоказано в программе 5.14, которая является непосредственным обобщением программы 5.5 обхода связного списка.
Для реализации обходов в других порядках достаточно соответствующим образом переставить вызовы функций в программе 5.14
Программа 5.14 Рекурсивный обход дерева
Эта рекурсивная функция принимает в качестве аргумента ссылку на дерево ивызывает функцию visit для каждого из узлов дерева.
В приведенном виде функция реализует прямой обход; если поместить обращение к visit между рекурсивными вызовами, получится поперечный обход; а если поместить обращение к visit после рекурсивных вызовов — то обратный обход.

Void traverse(link h,void visit(link))
{
if (h==0)return;
visit (h);
traverse(h->1,visit);
traverse(h->r,visit);
}
С этими же основными рекурсивными процессами, на которых основываются различные методы обхода дерева, мы уже встречались в рекурсивных программах типа"разделяй и властвуй" и в арифметических выражениях.
Например, выполнение прямого обхода соответствует рисованию вначале меток на линейке, а затем выполнению рекурсивных вызовов; выполнение поперечного обхода соответствует перемещению самого большого диска в решении задачи о ханойских башнях между рекурсивными вызовами, которые перемещают все остальные диски; выполнение обратного обхода соответствует вычислению постфиксных выражений и т.д.
Эти соответствия позволяют немедленно заглянуть внутрь механизмов, лежащих в основе обхода дерева.
Например, известно, что при поперечном обходе каждый второй узел является внешним, по той же причине, по какой при решении задачи о ханойских башнях каждое второе перемещение затрагивает маленький диск.
Полезно также рассмотреть не рекурсивные реализации, в которых используется явный стек.
Для простоты мы начнем с рассмотрения абстрактного стека, содержащего элементы дерева, инициализированного деревом, которое требуется обойти.
Затем мы войдем в цикл, в котором выталкиваетсяи обрабатывается верхняя запись стека, и который продолжается, пока стек не опустеет.
Если вытолкнутая запись является элементом, мы посещаем его; если вытолкнутая запись — дерево, мы выполняем последовательность операций сталкивания, которая зависит от требуемого порядка:
- Для прямого обхода заталкивается правое поддерево, затем левое поддерево, а затем узел.
- Для поперечного обхода заталкивается правое поддерево, затем узел, а затем левое поддерево.
- Для обратного обхода заталкивается узел, затем правое поддерево, а затем левое поддерево.
Нулевые деревья в стек не заталкиваются.
Методом индукции можно легко убедиться, что для любого бинарного дерева этот метод приводит к такому же результату, как и рекурсивный метод.
Traverse E
Visit E
Traverse D
Visit D
Traverse B
Visit B
Traverse A
Visit A
Traverse *
Traverse *
Traverse C
Visit C
Traverse *
Traverse *
Traverse *
Traverse H
Visit H
Traverse F
Visit F
Traverse *
Traverse G
Visit G
Traverse *
Traverse *
Traverse *

Описанная в предыдущем абзаце схема является концептуальной, охватывающейтри метода обхода дерева, однако реализации, используемые на практике, несколько проще.
Например, для выполнения прямого обхода не обязательно заталкиватьузлы в стек (мы посещаем корень каждого выталкиваемого дерева), поэтому можновоспользоваться простым стеком, состоящим только из одного типа элементов (связей дерева), как это сделано в не рекурсивной реализации в программе 5.15. Системный стек, поддерживающий рекурсивную программу, содержит адреса возврата и значения аргументов, а не элементы или узлы, но фактическая последовательностьвыполнения вычислений (посещения узлов) остается одинаковой для рекурсивногометода и метода с использованием стека.
Программа 5.15 Прямой обход (не рекурсивная реализация)
Эта нерекурсивная функция с использованием стека — функциональный эквивалент еерекурсивного аналога, программы 5.14.
Void traverse (link h, void visit (link))
{Stack s(max);
s.push(h);
while (!s.empty())
{
visit(h=s.pop());
if (h->r !=0) s.push(h->r);
if (h->1 !=0) s.push(h->1);
}
}
Четвертая естественная стратегия обхода — простое посещение узлов дерева в порядке, в котором они отображаются на странице — сверху вниз и слева направо.
Этот метод называется обходом по уровням, поскольку все узлы каждого уровня посещаются вместе, по порядку.
Как ни удивительно, обход по уровням можно получить, заменив в программе 5.15 стек очередью, что демонстрирует программа 5.16. Для реализации прямого обхода используется структура данных типа "последним вошел, первым вышел" (LIFO); для реализации обхода по уровням используется структура данных типа "первым вошел, первым вышел" (FIFO).
Эти программы заслуживают внимательного изучения,
поскольку они представляют существенно различающиеся подходы к организации остающейся невыполненной работы.
В частности, обход по уровням не соответствует рекурсивной реализации, связанной с рекурсивной структурой дерева.
Программа 5.16 Обход по уровням
Изменение структуры данных, лежащей в основе прямого обхода(см. программу 5.15) со стека на очередь приводит к преобразованию обхода в обход по уровням.
Void traverse(link h,void visit(link)
{queue q(max);
q.push(h);
while (!q.empty())
{
visit (h=q.get());
if (h->1 !=0) q.put(h->1);
if (h->r !=0) q.put(h->r);
}
}

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