Древовидная организация данных. Алгоритм построения упорядоченного бинарного дерева.

Древовидная организация данных (дерево) – множество записей, расположенных по уровням следующим образом:
-На 1 уровне расположена только 1 запись – корень дерева.
-К любой записи i-го уровня ведет адрес связи только первой записи уровня i-1 (предшествующй уровень).
Количество уровней в дереве –ранг.
Записи дерева, которые адресуются от общей записи (i-1) уровня, образуют группу.
Максимальное число элементов в группе – порядок дерева.
Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-го уровня называется обратным.
Вени связи – набор адресов связи, которые принадлежат к одной записи.
При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место.
Звено связи – набор адресов связи, принадлежащих к одной записи.
Если порядок дерева = р, то звено связи состоит из р+1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка.
Записи, у которых заполнены 2 адреса связи – полные.
Записи с 1-м заполненным адресом –неполные.
Записи с двумя незаполненными адресами – концевые.
В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ ее записи на ее правой ветви. Это определение также позволяет различать левые и правые адреса – ветви.
Алгоритм построения упорядоченного бинарного дерева:
1.Первая запись массива с ключом р(1) становится корнем дерева.
2.Значение ключа второй записи р(2) сравнивается с р(1), находящимся в корне дерева. Если р(2)р(i)), а при р(1)q, просмотр дерева продолжается по левой ветви корня, если р(1)q – производится переход к записи, расположенной на левой ветви р(i).
— p(i)