8 . Нелинейные структуры данных. Деревья и графы
Рассмотренные ранее структуры данных (массивы, массивы указателей и списки) имеют линейную структуру, единственный порядок обхода, который и определяет порядок следования (перечисления, логической нумерации) элементов. Деревья и графы, наоборот, представляют собой структуры, которые не допускают подобной «линеаризации»: их невозможно «вытянуть в линию» и для их изображения необходима плоскость. С точки зрения организации данных это дает разнообразие вариантов размещения одного и того же набора данных, а также различные варианты обхода одной и той же структуры.
8 .1. Деревья и рекурсивные алгоритмы
Определение дерева. Дерево и рекурсия
void ScanTree ( текущая вершина)<
if ( текущая вершина ==NULL) return;
for ( перебор потомков) ScanTree ( i -ый потомок)
Когда речь идет о древовидных структурах, следует отличать их абстрактное определение от конкретного способа их реализации в памяти. Последнее зависит также от вида алгоритмов, работающих с деревом:
— если используется рекурсивный или циклический алгоритм, начинающий работать с корневой вершины дерева, то необходимы только прямые ссылки от предка к потомкам;
— если алгоритм предполагает навигацию по дереву во всех направлениях, как вверх, так и вниз по дереву (например, в древовидной системе каталогов), то предполагается наличие как прямых, так и обратных ссылок от потомков к предкам (в системе каталогов – ссылка на родительский каталог);
— возможны алгоритмы, которые работают с деревом, начиная с терминальных вершин. Тогда кроме ссылок от потомков к предкам необходима еще структура данных, объединяющая терминальные вершины (например, массив указателей).
Способы представления деревьев
До сих пор мы говорили о деревьях абстрактно, как о логической структуре. А теперь спустимся на грешную землю и обсудим варианты его физического размещения. Составными частями физического представления дерева могут быть массивы, списки, массивы указателей. Начнем с самого простого.
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 scan _2( int A[], int n, int k,int level)< // k – индекс текущей вершины
printf(«l=%d node=%d val=%d\n»,level,k,A[k]);
// 0 1 2 3 4 5 6 7 8 9
Получается быстро, а главное, без дополнительной информации, индекс массива однозначно определяет положение вершины. Но за это приходится расплачиваться. Каждый следующий уровень требует удвоения размерности массива, вне зависимости от того, сколько вершин этого уровня используются. Поэтому основное требование – сбалансированность. Если есть хотя бы одна ветвь, сильно отличающаяся по длине, то эффективность использования памяти резко снижается. Если же дерево вырождается в список, то размерность массива растет экспоненциально W=2 N .
Каждая вершина содержит два указателя – на «старшего сына» – заголовок списка следующего уровня, и на «следующего брата» — ссылка в списке вершин текущего уровня.
// Представление дерева в виде разветвляющегося списка
ltree *son,*bro; // Указатели на старшего сына
>; // и младшего брата
ltree A=<"aa",NULL,NULL>, // Последняя в списке
C=<"cc",NULL,&B>, // Список потомков — концевых вершин A,B,C D =<" dd ", NULL , NULL >,
F=<"ff",&D,&E>, // Список потомков G — вершин F,E
void scan_l(ltree *p, int level)<
if (p==NULL) return;
for (ltree *q=p->son;q!=NULL;q=q->bro)
int n ; // Количество потомков в МУ
void scan(tree *p, int level)<
if (p==NULL) return;
Эффективность алгоритмов, работающих с деревьями
Можно провести аналогии между парой «деревья — рекурсивные алгоритмы» и «пространство-время». При работе рекурсивной программы происходит развертке дерева вызовов функции во времени, а дерево, как структура данных, выглядит как отображенный в памяти результат выполнения рекурсивного алгоритма. Именно поэтому к деревьям применимы выводы относительно эффективности рекурсивных алгоритмов:
— полный рекурсивный обход дерева имеет линейную трудоемкость;
— явный результат рекурсивной функции предполагает его накопление в процессе выполнения цепочки возвратов из рекурсивной функции (т.е. накопление результат идет в обратном направлении – от потомков к предку). При этом каждая вершина, получая результаты от потомков, вносит собственную «ложку дегтя», т.е. объединяет результаты поддеревьев с собственным;
— возможно использование формального параметра – ссылки, которая передается по цепочке рекурсивных вызовов. В этом случае все рекурсивные вызовы ссылаются на общую переменную, которая играет роль глобальных данных, используемых для накопления результата.
N = 1 + m + m 2 + m 3 + … + m L m L , L
В самом худшем случае при наличии только одного потомка в каждой вершине дерево вырождается в список, в этом случае длина ветви равна количеству вершин без 1.
для вырожденного в список дерева – линейной. Здесь возникают две проблемы. Во-первых, поддержка сбалансированности дерева. Для нее имеется два решения:
— использование алгоритмов, сохраняющих сбалансированность дерева, которые являются значительно более сложными, чем обычно, поскольку используют различные топологические преобразования групп смежных вершин дерева (причем рекурсивно);
— периодическое выравнивание (балансировка) дерева, возможно с использованием дополнительной структуры данных. Данное решение позволяет использовать простые алгоритмы работы с деревом, но требует слежения за его сбалансированностью (заметим, что это могут делать те же самые алгоритмы, например, определяя длину ветви при поиске заданного значения). Процедура балансировки может быть достаточно трудоемкой, но вызываемой сравнительно редко.
На житейском уровне эту альтернативу можно сформулировать как «идеальный порядок или периодическая генеральная уборка». Аналогичная ситуация возникает в любых системах динамического распределения и утилизации ресурсов: в системе динамического распределения памяти (2.6), при планировании двоичного файла (9.2), в системе управления файлами операционной системы, где она имеет похожие решения.
Вторая проблема упирается в основания, которые имеет алгоритм для однозначного выбора единственного потомка в каждой вершине (художественная аналогия — «рыцарь на распутье»). Здесь опять же возможны два подхода:
— наличие в вершине дополнительной (избыточной) информации, позволяющей сделать такой выбор «здесь и сейчас»;
— наличие определенного порядка размещения данных в дереве.
Источник
Бинарные деревья поиска и рекурсия – это просто
Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.
Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.
Рис. 1 Бинарное дерево
Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.
Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.
Рис. 3 Сбалансированное бинарное дерево поиска
Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.
Рис. 4 Экстремально несбалансированное бинарное дерево поиска
Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).
Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.
Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).
Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.
С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.
Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.
DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).
Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.
Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.
Рис. 5 Вспомогательный рисунок для обходов
Для бинарных деревьев поиска симметричный обход проходит все узлы в отсортированном порядке. Если мы хотим посетить узлы в обратно отсортированном порядке, то в коде рекурсивной функции симметричного обхода следует поменять местами правого и левого потомка.
Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение банкета статьи.
Источник
