4.2. Физическое представление иерархических структур

Рассмотрим физическое представление древовидных структур на примере операции обновления дерева с использованием сле­дующих методов.

1. Физически последовательное размещение.

2. Указатели.

3. Цепи и кольца.

На рис. 4.5 и 4.6 представлен пример иерархической структуры до и после обновления.

Рис. 4.5. Пример древовидной структуры

Записи, относящиеся к разным уровням дерева, обычно рас­сматриваются как главные и детальные. Поэтому при реализации такого файла для любой пары уровней дерева есть возможность выбора вариантов включения сегментов нижнего уровня и сегменты верхнего уровня. Хотя, исходя из стремления к однородности мас­сивов, обычно все сегменты нижнего уровня размещаются отдельно от сегментов верхнего уровня.

Рис. 4.6. Пример древовидной структуры после обновления

4.2.1. Физически последовательное размещение

На рис. 4.7 и 4.8 представлен пример реализации иерархическом структуры до и после обновления путем физически последователь­ного размещения данных на носителе.

Рис. 4.7. Пример реализации древовидной структуры до обновления

Рис. 4.8. Пример реализации древовидной структуры после обновления

Последовательность элементов на рис. 4.7 иногда называется левосписковой структурой (последовательность типа «сверху вниз — слева направо»).

Последовательность строится следующим образом: выбираются узлы, начиная от вершины дерева и вниз по самой левой ветви де­рева; когда выбран узел самого нижнего уровня этой ветви, выбираются подобные узлы слева направо; процесс повторяется, причем уже выбранные узлы пропускаются.

При размещении каждой записи последовательности в памяти может указываться, к какому уровню дерева она относится. Это вы­полняется путем введения в каждую запись специального кода (на­пример, тип записи может быть определен по типу ключа). Возмож­но также использование некоторой формы разграничения последо­вательности записей, например, представление записи в таком виде:

А1(В2(С5С12С6)В1(С12С9)ВЗ(С14С11С7С18))

Последовательные левосписковые структуры не позволяют осуществлять быстрый выбор элементов нижних уровней дерева, так как при этом требуется просмотр всего списка.

4.2.2. Левосписковые структуры с переполнениями

Включение и удаление элементов могут быть им полнены с помо­щью метода переполнения или метода распределенной свободной памяти, рассмотренных ранее на примере метода ведения файлов с индексно-последовательной организацией данных.

На рис. 4.9 и 4.10 представлен пример реализации иерархиче­ской структуры до и после обновления путем использования облас­ти переполнения.

Рис. 4.9. Пример реализации древовидной структуры методом переполнения

Рис. 4.10. Пример реализации древовидной структуры методом переполнения после обновления

В этом случае для определения местонахождения записей А, В или С можно использовать индексы.

4.2.3. Использование указателей на «подобные» и «порожденные»

Для обеспечения эффективных процедур выборки записей могут использоваться межзаписные ссылки следующих типов:

• указатели на порожденные записи;

• указатели на подобные записи;

• указатели на исходные записи.

При построении древовидных структур, в которых используется какой-либо один тип указателя, всегда исходят из альтернативы ме­жду сложностью реализации списка указателей переменной длины на порожденные записи и увеличением времени поиска, связанным с использованием цепочки указателей на подобные записи.

Практически эффективные компромиссы могут быть достигну­ты путем использования в каждой записи двух указателей каких-либо двух типов (рис. 4.11), а также использованием кольцевых струк­тур (например, рис. 4.12).

Рис. 4.11. Пример реализации древовидной структуры (см. рис. 4.5) с использо­ванием ссылок «порожденный — подобный» (штрихованные области означают конец списка)

Рис. 4.12. Пример реализации древовидной структуры с использованием кольцевых ссылок

На рис. 4.12 ссылки образуют кольца двух типов: подобных за­писей и кольца «исходный порожденный». В записях самого ниж­него уровня показаны указатели на исходные записи. Для единооб­разия здесь каждая запись имеет два указателя. Однако кольца боль­шей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.