Теория экономических информационных систем


Теория экономических информационных систем - стр. 68


 


                                        S                                                    P

 

Рис. 18. Представление древовидной организации данных в памяти ЭВМ

Назовем звеном связи набор адресов связи, принадлежащих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка. В качестве примера размещения дерева в памяти ЭВМ на рис. 18 показан один из возможных вариантов представления дерева с рис. 17, обратные адреса связи не показаны.

Рассмотрим бинарные  деревья (порядка 2 ). Они интересны тем, что составляющие их записи могут быть упорядочены. Для этого один из атрибутов записи должен быть объявлен ключевым.

Чтобы определить понятие упорядоченности бинарных деревьев, требуется ввести ряд новых понятий. В качестве примера рассмотрим бинарное дерево на рис. 19 (внутри показаны значения ключевого атрибута). Запись А - корень дерева. Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом - неполными, записи с двумя незаполненными адресами - концевыми. На рис. 19 записи А, В, Е, C- полные, G - неполная. D, F, T, H, R - концевые.

 


Рис. 19. Бинарное дерево

Адреса связи делятся на левые и правые. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует поддерево, адресованное из этой записи через правый (левый) адрес связи. В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой записи на ее правой ветви.

Упорядоченное бинарное дерево формируется из неупорядоченного массива записей по специальному алгоритму.

Вопросы и задания

1.                 Назовите критерии оценки методов организации данных.




Начало  Назад  Вперед



Книжный магазин