Деревья

Структура данных являющаяся B-деревом Степени 1, Страницы которого могут содержать только 2-вершины (вершины с одним полем и 2-мя детьми) и 3-вершины (вершины с 2-мя полями и 3-мя детьми). Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.

Красно – черные деревья

Это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный»

1. Узел либо красный, либо черный.

2. Корень — черный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на черный, но не обязательно наоборот).

3. Все листья — черные.

4. Оба потомка каждого красного узла — черные.

5. Всякий простой путь от данного узла до любого листового узла, содержит одинаковое число черных узлов.

28) Понятие графа. Способы представления графов. Операции над графами: добавление вершины, дуги. Создание графа.

Граф (graph) – объект, состоящий из множества кружков (точек) и множество соединяющих их линий. Кружки (точки) называются вершинами графа (nodes), линии со стрелками – дугами (arcs), без стрелок – ребрами.

Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным

Граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (орграф).

Способы представления графов в памяти

Матрица смежности – это матрица n× n, где n - число вершин. Строка с номером i содержит 1 в строке с номером j, если существует дуга из вершины i в вершину j.