1. Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующая запись).
2. Поместить запись с ключом F в первую позицию свободной памяти.
3. Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес - на адрес связи предшествующей записи, а последний - на первоначальное значение УСП.
ДРЕВОВИДНАЯ ОРГАНИЗАЦИЯ ДАННЫХ
ДРЕВОВИДНОЙ ОРГАНИЗАЦИЕЙ ДАННЫХ (деревом) называется множество записей, расположенных по уровням следующим образом:
• на 1-м уровне расположена только одна запись (корень дерева),
• к любой записи i-ro уровня ведет адрес связи только от одной записи уровня i-1.
Древовидная организация данных
Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом:
• на 1-м уровне расположена только одна запись (корень дерева),
• к любой записи i-ro уровня ведет адрес связи только от одной записи уровня i-1.
Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи (i-l)-ro уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-ro уровня называется обратным.
При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место.
Назовем звеном связи набор адресов связи, принадлежащих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка.
|
|
Рассмотрим деревья порядка 2 (бинарные). Для этого один из атрибутов записи должен быть объявлен ключевым.
Запись А - корень дерева.
Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом - неполными, записи с двумя незаполненными адресами - концевыми. На рис. записи А, В, Е, F - полные, С - неполная, D, H, I, J, К -концевые. Адреса связи делятся на левые и правые. Так, адрес от Е к Н - левый, от Е к I - правый. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует поддерево, адресованное из этой записи через правый (левый) адрес связи. У записи С правая ветвь состоит из записей F, I, К, левая ветвь пустая.
В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой
записи на ее правой ветви. Это определение позволяет также различать левые и правые адреса (ветви). Упорядоченное бинарное дерево формируется из неупорядоченного массива записей по специальному алгоритму. Этот алгоритм создает дерево из первой записи массива, затем -дерево из первых двух записей, из первых трех записей и так далее до исчерпания всех записей массива.