Лекция 13. Частично упорядоченные множества. Топологическая сортировка.
Примеры элементов, для которых определено отношение частичного порядка.
1. В толковом словаре слова определяются с помощью других слов. Если слово w определяется с помощью слова v, то это обозначается v < w. Топологическая сортировка означает такое расположение слов в словаре, при котором ссылки вперед отсутствуют.
2. В университетских программах некоторые курсы должны читаться раньше других. Если для курса w требуется знакомство с курсом v, то пишется v < w. Топологическая сортировка означает, что ни один курс не читается ранее тех, которые его поддерживают.
Частичный порядок на множестве S – это отношение между элементами множества S. Отношение порядка обозначается < , читается “предшествует” и удовлетворяет следующим аксиомам (для любых элементов S):
1) если x<y и y<z, то x<z (транзитивность)
2) если x<y, то не выполняется y<x (ассимитричность)
3) не выполняется x<x (иррефлективность)
Цели топологической сортировки – преобразовать частичный порядок в линейный. Графически это означает, что вершины графа нужно расположить на одной прямой так, чтобы все стрелки указывали вправо.
Частично упорядоченное множество.
Представление входных данных
1 < 2 2 < 4 4 < 6 2 < 10 4 < 8 6 < 3 1 < 3
3 < 5 5 < 8 7 < 5 7 < 9 9 < 4 9 < 10
Линейное расположение частично упорядоченного множества после сортировки
Описание структур данных программы
type
LPtr = ^leader;
TPtr = ^trailer;
leader = record // описание узла
key, // ключ (1, 2, ...)
count: integer; // число предшествующих
trail: TPtr; // ссылка на следующий узел
next : LPtr; // ссылка на список указателей, определяющих связи узлов
end;
trailer = record // описание связи узлов
id : LPtr; // ссылка на узел
next : TPtr; // ссылка на следующий элемент списка "описания связи узлов"
end;
1 < 2 2 < 4 4 < 6 2 < 10 4 < 8 6 < 3 1 < 3
3 < 5 5 < 8 7 < 5 7 < 9 9 < 4 9 < 10
Лекция 14. Определение дерева. Поддеревья, элементы дерева. Основные понятия и определения
Список (или последовательность) с базовым типом T - это:
либо пустой список (последовательность);
либо соединение элемента типа T и некоторого списка (последовательности) с базовым типом T.
Для определения принципов построения здесь используется рекурсия.
Определение дерева:
Дерево с базовым типом T – это:
1) либо пустое дерево;
2) либо некоторая вершина типа T с конечным числом связанных с ней отдельных деревьев с базовым типом T, называемых поддеревьями
Из сходства рекурсивных определений ясно, что список есть дерево, в котором каждая вершина имеет не более одного поддерева. Список (последовательность) иногда называют вырожденным деревом.
Упорядоченное дерево – это дерево, у которого ребра (ветви), исходящие из каждой вершины, упорядочены.
Вершина y, находящаяся непосредственно ниже вершины x, называется непосредственным потомком x. Вершина x называется непосредственным предком вершины y. Если x находится на уровне i, то y находится на уровне i+1. Корень дерева имеет уровень 0. Максимальный уровень какой-либо из вершин дерева называется глубиной или высотой дерева. Число непосредственных потомков данной вершины дерева называется ее степенью. Степень дерева – это максимальная степень всех вершин дерева. Длина пути к вершине x – это число ветвей или ребер, которое нужно пройти от корня дерева к вершине x. Корень имеет путь 0. Его потомки имеют путь 1.
Деревья второй степени называют двоичными или бинарными деревьями. Деревья степени больше двух называют сильно ветвящимися деревьями.
Упорядоченное двоичное дерево – это конечное множество элементов (вершин), которое либо пусто, либо состоит из корня (вершины) с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревом этого корня.
Дерево называется идеально сбалансированным, если число вершин в его левых и правых поддеревьях отличается не более чем на 1.
Порядок обхода двоичного дерева (R – корень, A и B – левое и правое поддеревья).
1. Сверху вниз (preoder): R, A, B (корень посещается ранее, чем поддеревья)
2. Слева направо (inorder): A, R, B .
3. Снизу вверх (postorder): A, B, R (корень посещается после поддеревьев).
