Битовые отображения

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

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

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

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

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

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

       Таблица 63

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

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

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

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

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

Таблица 66

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

             Таблица 67

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