Бинарное дерево

Особое значение прибрели бинарные деревья (binary tree)) упорядоченное дерево, каждая вершина которого или пустая или состоит из одного корня и двух бинарных поддеревьев.

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

Рис. 6.14. Сеть автомобильных дорог- а), сетевая структура данных - б), содержание узлов первого типа - в), содержание узлов второго типа - г)

С понятием «структура данных» тесно связано понятие «модель данных», что можно представить следующим образом:

Модель данных - это структура данных с заданными над ними операциями для обработки. Содержательно структура данных является составной частью модели данных.

Различают следующие базовые модели данных: реляционные(двумерные массивы), иерархические и сетевые. Кроме перечисленных известно множество моделей, отражающих цели их создателей (сущность-связь, бинарные модели, семантические сети и т.д.).

Реляционная модельосновывается на понятии “отношение”, и представляется совокупностью таблиц. На рис. 6.15 приведены базовые понятия данной модели.

Рис. 6.15. Основные понятия реляционной модели базы данных

Домен – это множество значений, принимаемых свойствами (характеристиками) отражаемого объекта.

Атрибут – это имя множества значений, входящих в домен. Атрибуты используются в качества средства для обращения к доменам.

Кортеж – это множество элементов из доменов, составляющих одну строку отношения (таблицы).

Отношение – это множество кортежей, отражающих свойства объекта.

Таблицы, входящие в реляционную модель, строятся в рамках ограничений, диктуемых операциями их обработки. Это следующие ограничения:

- таблица должна иметь имя (например, ДЕТАЛЬ, ПОСТАВЩИК, ПОСТАВКИ);

- таблица должна быть простой, то есть не содержать составных столбцов, например, у поставщика должен быть только один номер телефона;

- в таблице не должно быть одинаковых строк;

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

В компьютере таблицы реляционной модели обрабатываются с помощью операций реляционной алгебры.