Лекция 4: Базовые структуры данных. Деревья
Данный цикл лекций, как уже отмечалось, посвящен базовым структурам данных. Одной из таких является структура, имеющая огромное значение в практике программирования. В этой лекции мы рассмотрим понятие «дерево», виды деревьев, способы их представления в программах.
Дерево, фактически, является частным случаем графов, рассмотрение которых предполагается в одной из следующих лекций. Все термины, связанные с теорией графов, будут кратко разъяснены, а более полное и детальное их описание откладывается до соответствующей лекции.
Дерево – это связный ациклический неориентированный граф. Что же скрывается за этими загадочными словами?
Граф – множество вершин (V) и соединяющих их ребер (E), обозначается как G(V, E). В общем случае, упоминая графы, мы говорим о так называемых ориентированных графах, в которых имеет значение направление (т. е. вершины соединяют «линии со стрелками», называемые в русской литературе дугами). В неориентированных графах направление значения не имеет.
Путь из вершины u в вершину v – последовательность соединенных ребрами вершин <v0, v1, ..., vk>, где v0=u, vk=v. Путь, у которого начальная и конечная вершины совпадают, называется циклом. Ациклический граф – граф, не содержащий циклов.
Если любая вершина графа достижима (существует путь) из любой другой, то мы имеем дело со связным графом.
Рассмотрим свойства деревьев. Пусть мы имеем связный ациклический неориентированный граф G(V, E). Тогда следующие определения равносильны:
· G является деревом.
· Для любых двух вершин существует единственный соединяющий их простой путь.
· Граф связен, но перестает быть связным при удалении любого его ребра.
· Граф связен и количество ребер на единицу меньше количества вершин (|E|=|V|-1).
· Граф не содержит циклов и |E|=|V|-1.
· G ациклический, но добавление одного ребра приводит к появлению одного цикла.
Доказать эти свойства предлагается самостоятельно.
Если имеется (возможно) несвязный, но ациклический граф, можно говорить о лесе. Лес, как и положено, состоит из деревьев (компоненты связности графа). Многие алгоритмы обработки деревьев применимы и к лесам.
Дерево с корнем получается, если в дереве зафиксировать вершину, назвав ее корнем (root). Вершины корневого дерева по-английски называют «nodes».
Пусть x – произвольная вершина корневого дерева с корнем r. Существует единственный путь из r в x; все вершины, находящиеся на этом пути, мы называем предками (ancestors) вершины x. Если y является предком x, то x называется потомком (descendant). Каждую вершину принято считать своим предком и потомком.
Для каждой вершины x можно рассмотреть дерево, состоящее из всех потомков x, в которых x считается корнем. Оно называется поддеревом с корнем в x (subtree rooted at x).
Если (y, x) – последнее ребро на пути из корня в x, то y называется родителем (parent) x, а x – ребенком (child) y.
Корень является единственной вершиной, у которой нет родителя. Вершины, имеющие общего родителя, в английской литературе называют siblings; точного русского перевода этого слова нет, поэтому используется самое близкое по смыслу – братья. Вершина, не имеющая детей, называется листом (leaf). Вершины, имеющие детей, называются внутренними (internal).
Число детей у вершины корневого дерева называют ее степенью (degree). Длина пути от корня до произвольной вершины x называется глубиной (depth) вершины x. Максимальная глубина вершин дерева называется высотой (height) дерева.
Дерево с порядком на детях (ordered tree) – корневое дерево, множество детей для каждой вершины которого упорядочено: точно определено, какой из детей первый, какой второй и т. д.)
Двоичное дерево (binary tree) проще всего определить рекурсивно как некоторый набор вершин, который:
· либо пуст;
· либо разбит на три непересекающихся части: вершину, которая называется корнем (root), двоичное дерево, называемое левым поддеревом (left subtree) корня, и двоичное дерево, называемое правым поддеревом (right subtree) корня.
Двоичное дерево, которое не содержит вершин, называется пустым (empty). Если левое поддерево не пусто, то его корень называется левым ребенком (left child) корня всего дерева, если не пусто правое поддерево, то его корень носит название правого ребенка (right child) корня всего дерева. Если левое или правое поддеревья пусты, говорят что у корня нет левого либо правого ребенка (child is absent).
Вы спросите, почему бы не определить двоичное дерево как дерево с порядком на детях, в котором степень каждой вершины не превосходит 2. Все просто. В дереве с порядком на детях для вершин степени 1 не будет иметь значения, каким является единственный ребенок – левым или правым.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
