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

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

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

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

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

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

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

Таблица 63

Обозначения строк	Обозначения столбцов
01-АС	01-ИЭ
Иванов И.И.
Сидоров С.С.
Федоров Ф.Ф.
Яковлев Я.Я.

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

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

№ п/п	ФИО старосты группы		№ п/п	Домашний адрес
	Федоров Ф.Ф.			ул. Кирова, 3 - 4
	Яковлев Я.Я.			пр. Мира, 5 - 4
				ул. Репина, 1 - 2
				ул. Маркса, 2 - 2

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

Таблица 66

Ссылки	→	Т64,1	Т64,2
↓	Обозначения	01-АС	01-ИЭ
Т65,1	Иванов И.И.
Т65,2	Сидоров С.С.
Т65,3	Федоров Ф.Ф.
Т65,4	Яковлев Я.Я.

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

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

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

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

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

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

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

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

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

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

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

ФИО студента	Шифр учебной группы
Комаров К.К.	01-АС

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

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

Таблица 67