Лекция: Деревья .Графы

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

Корневой узел — самый верхний узел дерева.

Корень — одна из вершин, по желанию наблюдателя.

Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.

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

Арность дерева — количество ветвей из корня.

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

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

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

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

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

---------

Операции над деревьями:

— удаление элементов (при удалении корня возникают новые деревья)

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

удаление элементов приводит к изменению структуры

Если два корня, то нельзя попасть из одного корня в другой!!! Так как общее у них — только основная часть.

13.2. Графы

Граф — это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

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

Основная задача графа — поиск оптимального пути.

В машине граф представляется как «матрица инциденций»: — такие матрицы симметричны относительно диагонали. НО только у неориентированных (ненаправленных графов)

13.2.1. Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными.

Ориентированный и неориентированный графы являются частными случаями смешанного.