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


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


В последнем случае число пересылок адресов связи всегда одинаково и не зависит от числа записей в цепном каталоге, поэтому затраты времени на поиск при корректировке являются доминирующими и время корректировки пропорционально количеству записей Т~М.

§ 3.5. Древовидная организация данных

Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом:

•на 1-м уровне расположена только одна запись (корень дерева),

• к любой записи i-го уровня ведет адрес связи только от одной записи уровня i-1.

В данном определении понятия "дерево" и "уровень" вводятся одновременно. Если записи получат номера уровней, соответствующие определению, то они получат и древовидную организацию.

Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи (i-1)-го уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. В дереве на рис. 17 порядок равен 3 и ранг составляет 4 (записи дерева обозначены заглавными латинскими буквами).

Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-го уровня называется обратным.

При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место.

 


Рис. 17. Пример древовидной организации данных


                                                   А

 


           В                                     С                                       D

 


Ø

 

Ø

 

Ø

 

Ø

 

Ø

 

Ø

 

Ø

 

                                                   

                                                   M                                            K

                  N                                                                        




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