Битовые отображения. Структура дерева представляется бинарной матрицей

Структура дерева представляется бинарной матрицей. Вначале формируются обозначения столбцов и строк матрицы следующим образом:

1. выписываются обозначения столбцов, начиная с первого столбца, - им соответствуют обозначения элементов первого уровня иерархии дерева;

2. затем выписываются обозначения элементов второго уровня иерархии в качестве обозначений строк;

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

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

Например, для дерева рисунка 7 битовое отображение будет соответствовать таблице 63:

Таблица 63

В случае если элементы дерева имеют структуру, она представляется отдельно. Например, если для элементов дерева рисунка 7 надо также хранить информацию таблиц 48 и 49, она помещается в таблицы, подобные таблицам 64 и 65:

Таблица 64 Таблица 65

В этом случае бинарная матрица модифицируется и примет вид таблицы 66:

Таблица 66

Рассмотрим, как решаются в этих структурах задачи просмотра.

Пример 27. Пусть надо сформировать список студентов, учащихся в группе 01-АС, т.е. q^{просмотр} = (Шифр учебной группы =01-АС, ФИО студента), где К_доступ = 01-АС. Дерево описано в таблице 63.

Решение задачи:

1. по столбцам матрицы (таблица 63) определяем элемент дерева 01-АС – это элемент первого столбца;

2. определяем порожденные элементы для него – это те обозначения строк, для которых элемент матрицы равен 1, т.е. Федоров Ф.Ф. Алгоритм заканчивает работу.

Пример 28. Пусть надо определить, в какой группе учится студент Сидоров С.С., т.е. q^{просмотр} = (ФИО студента =Сидоров С.С., Шифр учебной группы), где К_доступ = Сидоров С.С.

Решение задачи:

1. по строкам матрицы (таблица 63) находим нужного студента – это элемент, расположенный во второй строке;

2. определяем элемент матрицы, равный 1, для второй строки – это элемент, расположенный во втором столбце, имеющем обозначение 01-ИЭ. Алгоритм заканчивает работу.

Рассмотрим задачу добавлениянового элемента.

Пример 29. Пусть в дереве рисунка 7 (описание дерева соответствует таблице 63) надо разместить элемент со структурой:

т.е. q^{добавление} = (ФИО студента =Комаров К.К., Шифр учебной группы =01-АС), где К_доступ = Комаров К.К., 01-АС.

После включения элемента дерево приобретет вид рисунка 8, а его описание будет соответствовать таблице 67 (новые данные выделены заливкой):

Таблица 67