Иерархическое представление данных деревья

Деревья

Дерево — это нелинейная иерархическая структура данных. Она состоит из узлов и ребер, которые соединяют узлы.

Зачем нужны деревья

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

Разные древовидные структуры позволяют быстрее и легче получать доступ к данным, поскольку дерево — структура нелинейная.

Части дерева

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

Другие понятия

• Высота узла — это максимальная длина пути от этого узла к самому нижнему узлу (листу).
• Глубина вложенности узла — длина пути от корня до этого узла.
• Высота дерева — это высота корневого узла или глубина самого глубокого узла.
• Степень узла — это общее количество ребер, которые соединены с этим узлом.

• Лес — множество непересекающихся деревьев. Например, если «срезать» корень, получится лес.

Виды деревьев

Обход дерева

Чтобы выполнить какую-либо операцию с деревом, нужно добраться до определенного узла. Для этого и существуют алгоритмы обхода дерева. Они помогают «дойти» до необходимого узла.

Где используются

• Деревья двоичного поиска помогают быстро проверить наличие элемента в наборе.
• Куча — это тоже своеобразное дерево. Кучи используют в алгоритме сортировки кучей.
• Префиксные деревья используются в маршрутизаторах, они хранят информацию о маршруте.
• Большинство популярных баз данных основаны на B-деревья и T-деревья.
• Компиляторы используют абстрактное синтаксическое дерево, чтобы находить синтаксические ошибки в ваших программах.

СodeСhick.io — простой и эффективный способ изучения программирования.

2023 © ООО «Алгоритмы и практика»

Источник

Иерархическая модель данных

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

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

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

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

1. Имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;
2. Во все остальные вершины заходит только одно ребро, а исходит произвольное (0, 1, 2, . n) количество ребер;
3. Нет циклов.

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

В программировании используется другое определение дерева, позволяющее при решении задач рассматривать дерево как структуру, состоящую из меньших деревьев (или поддеревьев), т.е. как рекурсивную структуру.

Рекурсивно дерево определяется как конечное множество T, состоящее из одного или более узлов (вершин), таких, что:

1. Существует один специально выделенный узел, называемый корнем дерева;
2. Остальные узлы разбиты на m>=0 непересекающихся подмножеств T₁, T₂, . T_m, каждое из которых в свою очередь является деревом.

Деревья T₁, T₂, . T_n называются поддеревьями корня. Из определения следует, что любой узел дерева является корнем некоторого поддерева, содержащегося в полном дереве. Число поддеревьев узла называют степенью узла. Узел называется концевым, если он имеет нулевую степень. Иногда концевые узлы называют листьями, а ребра — ветвями. Узел, не являющийся ни корнем, ни концевым узлом, называется узлом ветвления.

Таким образом, иерархическая древовидная структура, ориентированная от корня, удовлетворяет следующим условиям:

на первом уровне (i=1, самый верхний уровень иерархии дерева) может находиться только один узел — корневой; — на нижних уровнях (i=2,3. n) находятся порожденные (зависимые) узлы; — каждый порожденный узел, находящийся на уровне i, связан только с одним непосредственно исходным узлом (непосредственным родительским узлом), находящимся на более верхнем уровне (i-1) иерархии дерева;

• каждый исходный узел может иметь один или несколько непосредственно порожденных узлов, которые называются подобными;
• доступ к каждому порожденному узлу выполняется через его непосредственно исходный узел;
• существует единственный иерархический путь доступа к любому узлу, начиная от корня дерева (рис.28), например ,путь ABEI.

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

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

Графическая диаграмма схемы базы данных для иерархической базы данных называется деревом определения.

Вершины дерева определения БД соответствуют введенным типам групп записей, с помощью которых выполнена интерпретация типов сущностей.

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

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

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

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

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

Иерархия — это разновидность сети, являющаяся совокупностью деревьев (лесом), в которой все связи направлены от отца к сыну.

Рассматривая этот тип моделей, будем использовать терминологию сетевых моделей, введя дополнительное понятие — тип виртуальной логической записи (необходим, когда хотим поместить какой-либо тип записи в два или более деревьев иерархии или в нескольких местах в одном дереве). Такая запись представляет собой указатель на логическую запись некоторого типа и устраняет избыточность.

С помощью типов виртуальных записей можно преобразовать любую сеть в иерархию.

Источник