Иерархичная информация

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

Рисунок 1.

Такая структура, в которой одни элементы «подчиняются» другим, называется иерархия (от древнегреческого ἱεραρχία – «священное правление»). В информатике иерархию называют деревом. Дело в том, что если перевернуть эту схему вверх ногами, она становится похожа на дерево.

Несколько деревьев образуют лес.

Дерево состоит из узлов и связей между ними (они называются дугами). Первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка‐дуга) – это корень дерева. Узлы, из которых не выходит ни одна дуга, называются листьями и они называются конечными узлами. Все остальные узлы, кроме корня и листьев – это промежуточные узлы.

Из двух связанных узлов тот, который находится на более высоком уровне, называется «родителем», а другой – «сыном». Корень – это единственный узел, у которого нет «родителя»; у листьев нет «сыновей».

Используются также понятия «предок» и «потомок». «Потомок» какого‐то узла – это узел, в который можно перейти по стрелкам от узла‐предка. Соответственно, «предок» какого‐то узла – это узел, из которого можно перейти по стрелкам в данный узел.

Рисунок 2.

В дереве на рисунке справа родитель узла $E$ – это узел $B$, а предки узла $E$ – это узлы $A$ и $B$, для которых узел $E$ – потомок. Потомками узла $A$ (корня) являются все остальные узлы.

Типичными примерами иерархии могут быть различные классификации (растений, животных, минералов, химических соединений). Пример деления отряда Хищные приведен на рисунке $3$.

Рисунок 3. Отряд Хищные

В текстах иерархию часто оформляют в виде многоуровневого списка. Например, оглавление книги о хищниках может выглядеть так:

Рисунок 4.

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

Рисунок 5. Иерархия папок на компьютере

Алгоритм вычисления алгебрайческого выражения $(a+3)\cdot 5-2\cdot b$ может быть представлен в виде дерева:

Рисунок 6. Дерево алгоритма вычисления выражения $(a+3)\cdot 5-2\cdot b$

Листьями являются числа и переменные, а корнем и промежуточными узлами – знаки операций. Все вычисления идут «снизу вверх», от листьев – к корню. Приведенное дерево в виде математического механизма можно записать так:

Главное,что скобки здесь не обязательны; если их убрать, то выражение все равно может быть однозначно вычислено:

Такая запись называется префиксной (операция записывается перед данными), просматривается с конца. Логика записи следующая: как только встретится знак операции, то эта операция выполняется с двумя значениями, записанными справа. В рассмотренном выражении сначала выполняется умножение:

затем – сложение:

и еще одно умножение

и, наконец, вычитание: $(a+3)\cdot 5-(2\cdot b).$

Для того чтобы вычислять выражение не с конца, а с начала, префиксную форму «разворачивают» задом наперед, тогда получается постфиксная форма (операция после данных). Например, рассмотренное выше выражение может быть записано в виде $b 2 \cdot 5 3 a + \cdot -$

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

Можно выделить следующие виды иерархии информации: временная, пространственная, функциональная, ситуационная и информационная. Приведенное деление не может быть однозначным.

• Временная иерархия. Информация делится по времени поступления, обработки или отправки.

• Пространственная иерархия. Информация делится по пространственному признаку, а именно к какому узлу она относится.

• Функциональная иерархия. В ее основе лежит функциональная зависимость (подчиненность) элементов системы.

• Ситуационная иерархия. Информация делится в зависимости от ситуации, например все данные об каком-то одном объекте.