Программные операции с деревьями
Программная реализация структур данных при помощи операций с деревьями. Логическая эквивалентность древовидной структуры абстрактного дерева в теории графов. Логическое представление и изображение деревьев. Дерево, представленное с помощью массива.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 22.05.2018 |
| Размер файла | 284,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Деревья. Основные определения
Дерево - это граф, который характеризуется следующими свойствами:
· 1. Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ
· 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.
· 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.
Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).
Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.
рис. Дерево
рис. Лес
Ниже будет представлен важный класс орграфов - ориентированные деревья - и соответствующая им терминология. Деревья нужны для описания любой структуры с иерархией. Традиционные примеры таких структур: генеалогические деревья, десятичная классификация книг в библиотеках, иерархия должностей в организации, алгебраическое выражение, включающее операции, для которых предписаны определенные правила приоритета.
Ориентированное дерево - это такой ациклический орграф (ориентированный граф), у которого одна вершина, называемая корнем, имеет полустепень захода, равную 0, а остальные - полустепени захода, равные 1. Ориентированное дерево должно иметь по крайней мере одну вершину. Изолированная вершина также представляет собой ориентированное дерево.
Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны.
Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую - как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ.
Введем еще некоторые понятия, связанные с деревьями. На рис. показано дерево:
Узел X называется ПРЕДКОМ (или ОТЦОМ), а узлы Y и Z называются НАСЛЕДНИКАМИ (или СЫНОВЬЯМИ) их соответственно между собой называют БРАТЬЯМИ. Причем левый сын является старшим сыном, а правый - младшим. Число поддеревьев данной вершины называется СТЕПЕНЬЮ этой вершины. (В данном примере X имеет 2 поддерева, следовательно СТЕПЕНЬ вершины X равна 2).
рис. Дерево
Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называется ЛЕСОМ.
Логическое представление и изображение деревьев
Имеется ряд способов графического изображения деревьев. Первый способ заключается в использовании для изображения поддеревьев известного метода диаграмм Венна, второй - метода вкладывающихся друг в друга скобок, третий способ - это способ, применяемый при составлении оглавлений книг. Последний способ, базирующийся на формате с нумерацией уровней, сходен с методами, используемыми в языках программирования. При применении этого формата каждой вершине приписывается числовой номер, который должен быть меньше номеров, приписанных корневым вершинам присоединенных к ней поддеревьев. Отметим, что корневые вершины всех поддереьев данной вершины должны иметь один и тот же номер.
МЕТОД ВЛОЖЕННЫХ СКОБОК
(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))
Рис.. Представление дерева: а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна
Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину "дерево".
В системах, использующих файлы, программисты должны знать, где физически располагаются данные, формат записей, используемый прикладной программой. Рисунок 5.5 показывает формат записи файла дебиторских счетов.
Предположим, что программист хочет, чтобы отчет по кредитам показывал номер клиента, кредитный лимит и текущий баланс. Для того, чтобы написать программу, он должен знать позицию и длину нужных полей (например, что номер клиента занимает в записи с 1 по 10 позиции), а также формат каждого поля (текстовый или числовой). Процесс становится еще более сложным, если требуются данные из различных файлов.
СУБД преодолевают эту проблему, разделяя хранение и использование элементов данных. Метод баз данных обеспечивает два разных представления данных: логическое и физическое.
Логическое представление имеет дело с тем, как пользователи организуют, просматривают, понимают данные и их отношения.
Физическое представление имеет дело с тем, как и где данные физически размещаются и хранятся на дисках, магнитных лентах и других носителях. Рисунок 5.6 иллюстрирует эти два представления, используя данные дебиторских счетов.
Программа СУБД обеспечивает связь между тем, как данные физически хранятся на дисках и логическим представлением каждого пользователя. СУБД управляет базой данных так, чтобы пользователи могли получить к ним доступ, сделать запрос или откорректировать независимо от того, как и где данные физически хранятся. Пользователь отвечает только за определение логических требований к данным.
Отделение способа использования данных от того, как они хранятся и выбираются, означает, что пользователи могут менять свое логическое представление (требуемые элементы данных), не делая изменений в физическом представлении (физическом хранении данных). А администратор базы данных может изменить способ физического хранения данных, даже если пользователи не изменили связанные с ними прикладные программы.
Персонал, отвечающий за обработку данных, использует физическое представление, чтобы сделать эффективным использование памяти и вычислительных ресурсов. Администратор базы данных отвечает за такое физическое хранение данных, при котором логические требования пользователей могут быть удовлетворены. Однако программистам и пользователям обычно не нужно понимать физическое представление, поскольку они изначально заинтересованы в использовании данных независимо от того, как они хранятся.
3. Представление деревьев в памяти компьютера: последовательное и связанное размещение элементов.
Теперь мы обратимся к проблеме представления деревьев. Ясно, что изображение таких рекурсивных структур (точнее, рекурсивно определенных) с разветвлениями предполагает использование ссылок. Очевидно, что не имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указывающих на поддеревья данного узла.
Рис. 3.1. Выражение (a + b/c)*(d-- e'*J), представленное в виде дерева.
Ясно, что ссылка на пустое поддерево обозначается через nil. Следовательно, дерево на рис. 3.3. состоит из компонент такого типа и может строиться, как показано на рис. 3.2.
Ясно, что существуют способы представления абстрактной древовидной структуры в терминах других типов данных, например таких, как массив. Это -- общепринятый способ во всех языках, где нет средств динамического размещения компонент и указания их с помощью ссылок. и со значениями компонент, приведенными в табл. 3.1. Хотя подразумевается, что массив t представляет абстрактную структуру дерева, мы будем называть его все же не деревом, а массивом согласно явному определению. Мы не будем обсуждать другие возможные представления деревьев в системах, где отсутствует динамическое распределение памяти, поскольку мы считаем, что системы программирования и языки, имеющие это свойство, являются или станут широко распространенными.
Рис. 3.2. Дерево, представленное как структура данных.
Таблица 3.1. Дерево, представленное с помощью массива
|
* |
2 |
3 |
|
|
+ |
6 |
4 |
|
|
- |
9 |
5 |
|
|
/ |
7 |
8 |
|
|
* |
10 |
11 |
|
|
а |
0 |
0 |
|
|
Ь |
0 |
0 |
|
|
с |
0 |
0 |
|
|
d |
0 |
0 |
|
|
е |
0 |
0 |
|
|
f |
0 |
0 |
дерево программный граф логический
Прежде чем обсуждать, как лучше использовать деревья и как выполнять операции с деревьями, мы покажем на примере, как программа может строить дерево. Предположим, что нужно сформировать дерево, содержащее узлы типа, а значениями узлов будут п чисел, прочитанных из входного файла. Для усложнения задачи потребуем построить дерево с п узлами и минимальной высотой.
Чтобы достичь минимальной высоты при данном числе узлов, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие узлы поровну слева и справа от каждого узла. В результате построенное дерево при данном п имеет вид, как показано на рис. 3.3 для п = 1,..., 7. N = 3.
Рис. 3.3. Идеально сбалансированные деревья.
Правило равномерного распределения при известном числе узлов п лучше всего формулируется с помощью рекурсии:
1.Взять один узел в качестве корня.
2.Построить левое поддерево с nl = n div2 узлами тем же способом.
3.Построить правое поддерево с пг -- п -- nl-- 1 узлами тем же способом. Дерево идеально сбалансировано, если для каждого его узла количества узлов в левом и правом поддереве различаются не более чем на 1.
4.Предположим, например, что имеются следующие входные данные для дерева с 21 узлом:
21 8 9 11 15 19 20 21 7 3 2 15 6 4 13 14 10 12 17 16 18
Тогда алгоритм строит идеально сбалансированное дерево, показанное на рис. 3.4.
Рис. 3.4. Дерево.
Отметим простоту и ясность этой программы, достигнутые благодаря использованию рекурсивных процедур. Очевидно, что рекурсивные алгоритмы особенно уместны, когда программа должна обрабатывать данные, структура которых определена рекурсивно.
Преимущество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. Читателю предлагается проявить свою изобретательность и написать нерекурсивную программу, строящую такие же деревья, прежде чем смотреть на.Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя. Ему предлагается выяснить, как и почему она работает.
Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).
Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:
|
LPTR |
DATA |
RPTR |
где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.
Рассмотрим машинное представление бинарного дерева, изображенного на рис. 3.5.
Рис. 3.5 Логическое представление дерева
Рис. 3.6. Машинное связное представление дерева представленного на рис.3.5
Рассмотрим последовательное представление деревьев. Оно удобно и эффективно в случае, если древовидная структура в течение времени своего существования не подвергается значительным изменениям, за счет включения вершин, удаления вершин и т.д.
Выбор метода последовательного представления деревьев определяется также набором тех операций, которые должны быть выполнены над древовидными структурами. (Пример статистической древовидной структуры - пирамидальный метод сортировки). Простейший метод представления дерева в виде последовательной структуры заключается во введении вектора, задающего отбор для всех его вершин. Этот метод можно использовать также для представления леса. Недостаток метода - он не отображает упорядочения вершин дерева. Если в предыдущем примере поменять местами вершины 9 и 10, последовательное представление останется тем же.
Рис. 3.7. Диаграммы дерева: а) исходное б) перестройка в бинарное
Литература
Пышкин Е.В. Структуры данных и алгоритмы: реализация на C/C++. - СПб.: ФТК СПБГПУ
Размещено на Allbest.ru
Подобные документы
Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.
практическая работа [850,0 K], добавлен 16.04.2015Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.
курсовая работа [459,0 K], добавлен 09.08.2012Основные операции с АВЛ-деревьями, добавление и удаление элемента из сбалансированного дерева. Эффективность сортировки вставкой в АВЛ–дерево и итераторы. Алгоритм реализации АВЛ–деревьев через классы объектно–ориентированного программирования.
курсовая работа [281,1 K], добавлен 29.11.2010Изображения древовидной структуры. Десятичная система обозначений Дьюи. Стандартные формы представления деревьев. Представление деревьев с использованием списков, с использованием списков сыновей. Полное бинарное дерево. Основные операции над кучей.
презентация [495,0 K], добавлен 19.01.2014Пример дерева решений. Анализ древовидной структуры данных. Предикторные (зависимые) переменные как признаки, описывающие свойства анализируемых объектов. Решение задач классификации и численного прогнозирования с помощью деревьев классификации.
презентация [391,1 K], добавлен 09.10.2013Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.
презентация [330,6 K], добавлен 19.10.2014Организация работы базы данных с помощью сбалансированных В-деревьев: принципы, методы добавления, поиска, удаления элементов из структуры. Процедуры, производящие балансировку и слияние записей в блоке. Реализация программы в Научной библиотеке ОрелГТУ.
курсовая работа [95,3 K], добавлен 12.08.2011Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева.
контрольная работа [81,6 K], добавлен 14.12.2011Обоснование выбора языка и среды программирования. Обзор и анализ существующих программных решений. Разработка графического и пользовательского интерфейса. Алгоритм бинарного поиска. Методы добавления, удаления элемента из дерева и вывода на экран.
курсовая работа [1,3 M], добавлен 31.05.2016Понятие вложенных циклов, одномерных и двумерных массивов в программировании. Матрицы и основные действия с ними. Иерархические записи, понятие дерева. Операции с двоичными деревьями, рекурсия, включение и удаление узла. Алгоритм поиска по дереву.
отчет по практике [507,1 K], добавлен 27.12.2011
