Теория экономических информационных систем. Малова Е.А. - 30 стр.

отмечается нулевым значением.
    Древовидная организация данных.
    Деревом называется множество записей, расположенных по уровням
следующим образом:
    • на 1-м уровне расположена только одна запись (корень дерева),
    • к любой записи i-го уровня ведет адрес связи только от одной записи
уровня i - 1.
    Особенностью этой организации данных является то, что в дереве связаны
значения только одного отношения. (а в иерархической системе связаны раз-
личные отношения).
    Количество уровней в дереве называется рангом. Ранг определяет макси-
мальное число сравнений при поиске данных. Записи дерева, которые адресу-
ются от общей записи (i - 1)-го уровня, образуют группу. Максимальное число
элементов в группе называется порядком дерева. При размещении дерева в
памяти ЭВМ каждая запись может занимать произвольное место. (Рассмотрим
бинарные деревья).

                    Бинарные деревья (второго порядка)

     Каждый из уровней имеет только 2 выхода. Особенность – составляющие
его записи могут быть упорядочены. Для этого один из атрибутов записи объ-
является ключевым.
     Для определения упорядоченности необходимо ввести новые понятия.
     Записи, у которых заполнены 2 адреса связи, называются полными.
     Записи с одним заполненным адресом связи считаются неполными. Запи-
си, не имеющие адресов связи, называются концевыми.
     Каждая из ветвей образует поддерево (левое и правое).
     Каждая запись имеет левую и правую ветвь.
     ПРАВИЛО
     В упорядоченном бинарном дереве значение ключевого атрибута каждой
связи должно быть больше, чем значение ключа у любой записи левой её поло-
вины (ветви), и меньше, чем ключ любой записи на ее правой ветви.
     Упорядоченное бинарное дерево формируется из неупорядоченного мас-
сива записей по определенному алгоритму. Этот алгоритм создает дерево из
первой записи массива, затем – дерево из первых двух записей, из первых трех
записей и так далее до исчерпания всех записей массива.

     Алгоритм построения упорядоченного бинарного дерева. (стр. 162)

     1. Первая запись массива с ключом р(1) становится корнем дерева.
     2. Значение ключа второй записи р(2) сравнивается с р(1). Если р(2) <
р(1), то вторая запись помещается на левой от корня ветви. В противном случае
– на правой.
     3. Выбор места i- ой записи массива производится следующим образом.

                                     30