Рис. 1

Элементы H2, H3, H4 определяют "головы" новых наборов и од­но­временно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации дина­ми­чес­ких "вложенных" понятий предметной области. Например, в ассо­ци­ацию H1-"Акционеры" могут входить как отдельные частные ли­ца, так и коллективы - организации, которые являются ассо­циа­ци­я­ми собственных акционеров.

Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назы­вае­мых ортогональных списков, моделирующих структуры динамически изме­няющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", ра­­зу­меется, не означает, что ортогональные списки используются лишь в игровых задачах.

1.4.3. Дерево

Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется сово­купность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эле­мен­ты образуют поддеревья. Наиболее широко используется струк­ту­ра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.

К

Связь с левым потомком

Рис. 2

На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К – корень; Л1,Л2,Л3 – "листья" – вер­ши­ны с "пустыми" связями ("не выросшими" поддеревьями).

Заметим, что в этой интерпретации дерево реализуется на одно­род­ных списках (в отличие от набора). Особое положение корня оп­ре­деляется единственным свойством – отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева от­крывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и оп­ре­де­ляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения по­ряд­ка на множестве вершин.