Представление древовидных структур связанными линейными списками. Метод указателей на порожденные записи.

Дерево – это нелинейная структура данных, используемая для представления иерархических связей, имеющих отношение «один ко многим».

Дерево с базовым типом Т определяется рекурсивно либо как пустая структура (пустое дерево), либо как узел типа Т с конечным числом древовидных структур этого же типа, называемых поддеревьями.

Деревья используются при построении организационных диаграмм, анализе электрических цепей, для представления синтаксических структур в компиляторах программ, для представления структур математических формул, организации информации в СУБД и, кроме того, для более эффективного извлечения данных.

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

Корень дерева лежит на нулевом уровне. Максимальный уровень какой-либо вершины дерева называется ее глубиной (от корня до узла) или высотой (от узла до максимально удаленного листа). Отсюда максимальный уровень корня равен нулю. Максимальный уровень всех вершин называется глубиной дерева.

Число непосредственных потомков у вершины (узла) дерева называется степенью вершины (узла).

Максимальная степень всех вершин является степенью дерева. Число ветвей от корня к вершине есть длина пути к этой вершине.

Каждому узлу дерева можно сопоставить имя узла и значение узла, то есть собственно данные, хранящиеся в этом узле. Причем, если значением являются разнородные данные (записи или объединения), то значением узла можно считать значение одного из полей этих данных, называемого ключом.

Например, есть дерево (рис 1)

28. Операции, выполняемые над реляционными отношениями. Реляционная алгебра..Операции, выполняемые над реляционными отношениями. Реляционная алгебра. Операции реляционной алгебры манипулируют реляционными таблицами, то есть эти операции используют одну или две из существующих таблиц для создания новой таблицы. Затем полученная новая таблица может использоваться в качестве входной для новой операции. Реляционная алгебра состоит из следующих девяти операций:

• объединения;

• пересечения;

• разности;

• произведения;

• выбора;

• создания проекций;

• соединения;

• присвоения.

Объединением отношений называется отношение, содержащее множество кортежей принадлежащих либо первому, либо второму исходным отношениям, либо обоим одновременно. Формат операции объединения имеет следующий вид:

 

; R1 = {r1}; R2 = {r2}

Разностью отношений R1, R2 (R=R1\R2) называется множество кортежей принадлежащих R1, но не принадлежащих R2. Формат операции разности имеет следующий вид:

R1 = {r1}; R2 = {r2}

Пересечением отношений R1 и R2 называется отношение R той же арности, что и R1, R2 состоящее из кортежей принадлежащих одновременно как R1, так и R2. Формат операции пересечения имеет следующий вид:

R=R1?R2={r|r?R1?r?R2}.

Операция произведения.Эту операцию можно реализовывать над отношениями разной арности. Пусть имеются отношение R1 арности k1 и отношение R2 арности k2; тогда декартовым произведением отношений R1 и R2 (R1?R2) называется отношение R = k1+k2, элементы кортежей которых представлены следующим образом: Первые k1 элементы образуют кортежи отношения R1, а следующие k2 – кортежи отношения R2.

Операция соединения используется для связывания данных между таблицами. Это, наиболее важная функция любого языка баз данных. У нее есть несколько версий: естественное соединение, тета-соединение, внешнее соединение. Наиболее важным из них является естественное соединение.

Операция проекции позволяет получить из некоторого отношения R новое отношение, в которое выбираются отдельные столбцы отношения R и компонуются в указанном порядке