9.4. Деревья

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m  0 поддеревьев Т1, Т2, …, Тm.

Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами.

Рис. 9.9. Дерево с 11 узлами

Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.

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

В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 9.7 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д.

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

считаются различными.

Определим лес как упорядоченное множество деревьев.

Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого Tl и правого Tr.

Бинарные деревья, вообще говоря, не являются подмножеством множества

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

Различие между бинарным деревом и деревом состоит в том, что не бинарное дерево не может быть пустым, и каждый узел не бинарного дерева может иметь произвольное число поддеревьев. В то же время бинарное дерево может быть пустым и каждая его вершина может иметь 0, 1 или 2 поддерева, также существует различие между левым и правым поддеревьями.

10. Базы данных

10.1. Основные понятия

Базы данных – это совокупность определенным образом организованной информации на какую-либо тему (в рамках предметной области).

Например,

• База данных книжного фонда библиотеки;

• База данных кадрового состава учреждения;

• База данных законодательных актов в области уголовного права;

• База данных современных песен.

Базы данных бывают:

• Фактографические – содержатся краткие сведения об описываемых объектах, представленные в строго определенном формате;

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

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

База данных — организованная совокупность данных, предназначенная для длительного хранения во внешней памяти ЭВМ и постоянного применения.

Для хранения БД может использоваться как один компьютер, так и множество взаимосвязанных компьютеров. Если различные части одной базы данных хранятся на множестве компьютеров, объединенных между собой сетью, то такая БД называется распределенной базой данных.

Существует три типа моделей данных:

• Реляционная модель данных строится по принципу взаимосвязанных таблиц.

• Иерархическая - один тип объекта является главным, все нижележащие – подчиненными.

• Сетевая - любой тип данных одновременно может быть главным и подчиненным.

Для взаимодействия пользователя с базами данных используют системы управления данными (СУБД).

К современным СУБД относятся:

• Oracle,

• MS Access,

• MS SQL Server,

• Interbase,

• MySQL,

• IBM DB2.

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

• производительность и готовность.

• минимальные затраты.

• простота и легкость использования.

• простота внесения изменений.

• возможность поиска.

• целостность.

• безопасность и секретность.

Рис. 10.1. Схема работы с БД