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

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

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

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

до обновления

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

после обновления

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

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

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

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

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

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

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

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