Иерархические структуры

Иерархические структуры сложнее, чем последовательные. Типичным примером иерархической структуры является схема организации некой компании. Компания состоит из отделов, которые составлены из групп, сформированных из отдельных служащих. Такую структуру можно представить графически в виде перевернутого дерева, которое имеет корень, узлы, листья и ветви (рис. 9.31). Поэтому эту структуру называют древовидной структурой. Она будет подробнее рассмотрена в следующем разделе.

Общепринято графически представлять такую структуру в. виде перевернутого дерева. На самом верхнем уровне иерархии находится корень дерева. Из корня, а также из других элементов иерархии, называемых узлами, исходят ветви. Каждая ветвь изображает некую связь. На самом нижнем уровне дерева находятся листья. Древовидная структура характеризуется тем, что в ней: из каждого узла, за исключением листьев, исходит одна или более ветвей; каждый узел, за исключением корня, завершает одну и только одну ветвь от корня к каждому конкретному узлу существует только один путь.

Имеется много различных способов организации указателей, с помощью которых можно связывать данные в древовидной структуре. Чем больше предусмотрено типов указателей, тем быстрее осуществляется поиск данных, но медленнее и сложнее становится корректировка указателей и увеличивается объем необходимой памяти. На рис. 9.32 показаны наиболее часто применяемые связи между отдельными элементами структур различной степени сложности.

Выделяются два основных типа указателей. Указатель первого типа идентифицирует элемент на следующем верхнем или нижнем уровне. Такую связь называли связью типа отец — сын, а теперь (вероятно, из-за протестов со стороны феминистского движения) называют связью родитель — ребенок или, согласно терминологии группы DBTG [1], связью типа начальник — подчиненный. При этом расположенный выше элемент иерархии считается начальником (родителем, отцом), а связанные с ним нижние элементы рассматриваются как подчиненные (дети, сыновья). Указатели другого типа связывают элементы, расположенные в дереве на одном и том же уровне, образуя связи типа подчиненный — подчиненный (дети одних родителей — братья).

На диаграмме (h) пунктирными линиями указаны логические связи в дереве. На всех других диаграммах сплошные линии со стрелками изображают указатели, добавленные к начальным данным, для того чтобы можно было получить адреса логически связанных данных. (На диаграмме (g) указатели вверх и вниз представлены одной линией, а поля указателей объединены в одну точку, чтобы упростить рисунок.) В случае структур (а) и (с) доступ к данным возможен только сверху. Набор указателей в структурах (с) и (d) обеспечивает возможность последовательной обработки элементов одного и того же уровня только после доступа к элементу предшествующего верхнего уровня. При такой структуре, представленной, например, на рис. 9.31, на вопрос: «Кто товарищи по группе у АА1?» можно ответить, только находясь на уровне группы и используя указатели в группе АА, но нельзя, находясь на уровне АА1. При всех других структурах элементы, расположенные на одном и том же уровне, можно обрабатывать последовательно, не переходя для этого сначала на верхний уровень. Указатели, показанные на схемах (а) и (Ь), удобны в тех случаях, когда файл состоит из элементов с фиксированной длиной или когда все элементы данного уровня имеют одинаковую длину. Другие структуры более удобны для записей переменной длины, а также в тех случаях, когда важно знать, сколько записей существует на данном уровне или каково их размещение в начале обработки.

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


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Иерархические структуры Иерархические структуры сложнее, чем последовательные. Типичным примером иерархической структуры является схема организации некой компании. Компания состоит из отделов, которые составлены из групп, сформированных из отдельных служащих. Такую структуру можно представить графически в виде перевернутого дерева, которое имеет корень, узлы, листья и ветви (рис. 9.31). Поэтому эту структуру называют древовидной структурой. Она будет подробнее рассмотрена в следующем разделе. Общепринято графически представлять такую структуру в. виде перевернутого дерева. На самом верхнем уровне иерархии находится корень дерева. Из корня, а также из других элементов иерархии, называемых узлами, исходят ветви. Каждая ветвь изображает некую связь. На самом нижнем уровне дерева находятся листья. Древовидная структура характеризуется тем, что в ней: из каждого узла, за исключением листьев, исходит одна или более ветвей; каждый узел, за исключением корня, завершает одну и только одну ветвь от корня к каждому конкретному узлу существует только один путь. Имеется много различных способов организации указателей, с помощью которых можно связывать данные в древовидной структуре. Чем больше предусмотрено типов указателей, тем быстрее осуществляется поиск данных, но медленнее и сложнее становится корректировка указателей и увеличивается объем необходимой памяти. На рис. 9.32 показаны наиболее часто применяемые связи между отдельными элементами структур различной степени сложности. Выделяются два основных типа указателей. Указатель первого типа идентифицирует элемент на следующем верхнем или нижнем уровне. Такую связь называли связью типа отец — сын, а теперь (вероятно, из-за протестов со стороны феминистского движения) называют связью родитель — ребенок или, согласно терминологии группы DBTG [1], связью типа начальник — подчиненный. При этом расположенный выше элемент иерархии считается начальником (родителем, отцом), а связанные с ним нижние элементы рассматриваются как подчиненные (дети, сыновья). Указатели другого типа связывают элементы, расположенные в дереве на одном и том же уровне, образуя связи типа подчиненный — подчиненный (дети одних родителей — братья). На диаграмме (h) пунктирными линиями указаны логические связи в дереве. На всех других диаграммах сплошные линии со стрелками изображают указатели, добавленные к начальным данным, для того чтобы можно было получить адреса логически связанных данных. (На диаграмме (g) указатели вверх и вниз представлены одной линией, а поля указателей объединены в одну точку, чтобы упростить рисунок.) В случае структур (а) и (с) доступ к данным возможен только сверху. Набор указателей в структурах (с) и (d) обеспечивает возможность последовательной обработки элементов одного и того же уровня только после доступа к элементу предшествующего верхнего уровня. При такой структуре, представленной, например, на рис. 9.31, на вопрос: «Кто товарищи по группе у АА1?» можно ответить, только находясь на уровне группы и используя указатели в группе АА, но нельзя, находясь на уровне АА1. При всех других структурах элементы, расположенные на одном и том же уровне, можно обрабатывать последовательно, не переходя для этого сначала на верхний уровень. Указатели, показанные на схемах (а) и (Ь), удобны в тех случаях, когда файл состоит из элементов с фиксированной длиной или когда все элементы данного уровня имеют одинаковую длину. Другие структуры более удобны для записей переменной длины, а также в тех случаях, когда важно знать, сколько записей существует на данном уровне или каково их размещение в начале обработки. Можно также накладывать дерево на иерархическую структуру, связанные списки или другие структуры, которые в общем случае не зависят друг от друга. Если дерево представляет собой файл персонала с начальниками и подчиненными, то его можно наложить на ассоциативную структуру. Другие связи между элементами такого дерева могут указывать упорядочение элементов согласно размеру оклада и возрасту, т. е. описывать независимые списковые структуры, установленные над теми же самыми данными.