Определение бинарного дерева

Реферат

Данная работа выполнена в объеме: пояснительная записка на 33 страницах, 26 иллюстрациях, 3 таблицах, 7 источниках, 2 приложениях.

Ключевые слова: автоматизация, автоматизированное рабочее место, информационно-поисковая система, учет записей по всем культурам.

Объектом разработки является информационно поисковая система «Агроном».

Цель проектирования – получение практических умений в области ООП, применении различных компонентов среды разработки, приемов работы с языком программирования, а также изучение различных алгоритмов.

В процессе разработки выполнены следующие исследования:

– изучены способы применения интерфейсов в языке программирования C#;

– рассмотрены и применены на практике различные алгоритмы работы с бинарным деревом;

– улучшены навыки пользования различными компонентами среды разработки Visual Studio 2013.

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

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

Основные технико-эксплуатационные показатели: высокая скорость работы с данными, предельно низкие системные требования, а также низкая цена программного продукта.

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

Содержаник

ВВЕДЕНИЕ. 6

1 Бинарные деревья и их актуальность. 7

1.1 Назначение бинарных деревьев. 7

1.2 Определение бинарного дерева. 7

1.3 Алгоритм бинарного поиска. 8

1.4 Алгоритм вставки узлов. 10

1.5 Алгоритм удаления узлов. 11

2 Методика решения поставленой задачи и обоснование наравления разработки программного продукта. 13

2.1 Обоснование выбранного языка программирования. 13

2.2 Методика решения поставленной задачи. 13

3 Разработка программы.. 16

3.1 Диаграмма классов. 16

3.2 Проектирование интерфейса программы.. 17

3.3 Описание программных модулей. 17

3.4 Разработка, тестирование методов. 18

3.5 Тестирование программы с использованием ложных данных. 22

ЗАКЛЮЧЕНИЕ. 23

Список использованых источникав. 24

Приложение А.. 25

Руководство пользователю.. 25

Приложение Б. 29

Листинг программы.. 29

Перечень условных обозначений и сокращений

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

Вырожденное дерево – дерево, в котором левое поддерево пусто на каждом уровне и есть только правые поддеревья (или наоборот).

Граф – совокупность непустого множества вершин и наборов пар вершин.

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

Лист – узел, не имеющий указателя ни на левое поддерево, ни на правое.

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

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

Узел – корень поддерева. Каждый узел может иметь указатель на левое и (или) правое поддерево.

БД – база данных.

ДДП – двоичное дерево поиска.

ОО – объектно-ориентированный.

ООП – объектно-ориентированное программирование.

IP (Internet Protocol) – интернет протокол, адрес.

LINQ (Language-Integrated Query) – это набор функций, которые значительно расширают возможности таких языков, как C#и Visual Basic.

NET.Framework – программная платформа, основой которой является общеязыковая среда исполнения Common Language Runtime, которая подходит для разных языков программирования.

ВВЕДЕНИЕ

Каждый день мы сталкиваемся с огромными объемами информации: когда читаем книгу, смотрим фильм или же просто сидим в интернете. И с каждым днем этой информации становится все больше. То же самое и в программировании. Современные программы обрабатывают огромные объемы информации за считанные секунды. И это во многом заслуга бинарных деревьев поиска. Бинарное дерево (двоичное дерево) – иерархическая структура данных, в которой каждый узел имеет не более двух потомков [1]. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Для практических целей обычно используют два подвида бинарных деревьев – двоичное дерево поиска и двоичная куча.

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

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

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

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

Бинарные деревья и их актуальность

Назначение бинарных деревьев

Деревья являются одной из старейших и наиболее часто используемых структур данных в программировании. В самых общих чертах деревья – это просто неориентированные графы, называемые свободными деревьями. Однако наибольшее распространение получили бинарные деревья поиска. Бинарные деревья поиска упрочились в употреблении так сильно, что если кто-то говорит о деревьях, то подразумевается обычно бинарное дерево поиска.

Часто программам необходимо хранить огромные объемы информации. Это может быть гистограмма уникальных слов в файле, сортировка огромной кучи IP-адресов, с которых были установлены соединения на сокете или просто база данных адресов электронной почты. Ни массивы, ни связные списки не подходит для нужд, описанных выше. То, что нужно – это структура данных, которая хранит данные в отсортированном виде без необходимости совершать дополнительные телодвижения с простыми операциями вставки и удаления, а также эффективным поиском. Ни связный список, ни массивы не обладают такими свойствами, а потому они являются плохими решениями.

Определение бинарного дерева

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

– поиск вершины по ключу;

– определение вершин с минимальным и максимальным значением ключа;

– переход к предыдущей или последующей вершине, в порядке, определяемом ключами;

– вставка вершины;

– удаление вершины;

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

Таким образом, скоростные характеристики поиска в ДДП могут варьироваться от O(log₂N) в случае законченного дерева до O(N) – в случае вырожденного.

Не нашли, что искали? Воспользуйтесь поиском по сайту: