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

ИНФОРМАЦИОННЫХ СИСТЕМАХ

УРОВНИ ДАННЫХ В

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, битов. Такие данные имеют очень простую организацию, слабо структурированы.

Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры данных".

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

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

 

Логическая (абстрактная) структура данных - эторассмотрение структуры данных без учета ее представления в машинной памяти.

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

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

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

 

На уровне хранения (содержательный уровень)оперируют со структурами хранения-представления логической структуры данных в памяти ЭВМ.

Структура хранения должна полностью отображать логическую структуру данных и поддерживать ее в процессе функционирования системы.

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

Понятие "Физическая структура данных" отражает способ физического представления данных в памяти машины и называется еще структурой хранения или структурой памяти.

 

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

В иерархической структуре адрес каждогоэлемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу.

 

Дихотомия данных.Основным недостатком иерархических структур данных является увеличенный размер пути доступа. Очень часто бывает так, что длина маршрута оказывается больше, чем длина самих данных, к которым он ведет.

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

В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.

 

Древовидные структуры данных

Элементы древовидных структур данных (ДСД) располагаются на различных уровнях и соединяются с помощью адресов связи.

ДСД соответствует графу типа «дерево» и представляется набором элементов, распределенных по уровням иерархии следующим образом:

На первом уровне расположен только один элемент, который называется корнем дерева; к любому элементу k-го уровня ведет только один адрес связи; к любому элементу k-го уровня адрес связи идет только от элемента(k-1)-го уровня.

Количество уровней в ДСД называют рангом. Элементы дерева, которые адресуются от общего элемента (k-1)-го уровня, образуют группу.

 

Максимальное число элементов в группе называется порядком дерева. Деревья с порядком больше двух принято называть общими ДСД, а с порядком 2 – двоичными, или бинарными деревьями. Дерево порядка 1 – строчная структура.

В зависимости от количества элементов в группе некоторой вершины различают три типа вершин. Если n – порядок дерева, то вершины из n элементов называются полными, вершины, не имеющие группы – концевыми (листьями), а остальные – неполными.

Наиболее распространенным видом ДСД являются бинарные деревья, в которых каждая вершина k-го уровня содержит два адреса (правый и левый) связи на вершины (k+1)-го уровня и один (обратный) – на вершину (k-1)-го уровня.

 

Множество вершин, соединенных с данной вершиной через левый адрес связи, образует левую ветвь этой вершины. Аналогично определяется правая ветвь.

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

Записи снабжаются ключами с числовыми значениями. Каждый элемент в упорядоченном бинарном дереве (УБД) имеет на своей левой ветви элементы с меньшим, чем у него, значением ключа, а на правой ветви – элементы с большим или равным значением ключа.