Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Работа № 100170
Наименование:
Курсовик Исследование алгоритмов на базе дерева бинарного поиска
Информация:
Тип работы: Курсовик.
Предмет: Программирование.
Добавлен: 03.11.2016.
Год: 2016.
Страниц: 26.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
КУРСОВАЯ РАБОТА
по дисциплине: «Теория алгоритмов и математические основы представления знаний»
Тема: «Исследование алгоритмов на базе дерева бинарного поиска»
Оглавление
Введение……….3 1. Теоретическая часть………..4 2. Практическая часть………...10 2.1 Описание и пример работы алгоритма………...10 2.2 Блок-схема алгоритма………..13 2.3 Листинг и пример работы программы………14 2.4 Исследование алгоритма и его эмпирический анализ………..25 Выводы………...26 Литература……….27
Введение
В программировании и компьютерных науках структуры данных - это способы организации данных в компьютерах. Часто вместе со структурой данных связывается и специфический перечень операций, которые могут быть выполнены над данными, организованными в такую структуру. Правильный подбор структур данных является чрезвычайно важным для эффективного функционирования соответствующих алгоритмов их обработки. Хорошо построены структуры данных позволяют оптимизировать использование машинного времени и памяти компьютера для выполнения наиболее критических операций. Известная формула "Программа = Алгоритмы + Структуры данных" очень точно выражает необходимость ответственного отношения к такому подбору. Поэтому иногда даже не выбран алгоритм для обработки массива данных определяет выбор той или иной структуры данных для их сохранения, а наоборот. Поддержка базовых структуры данных, которые используются в программировании, включена в комплекты стандартных библиотек наиболее распространенных языков программирования, такие как Standart Template Library для C ++, Java API, Microsoft.net Целью курсовой работы является исследования бинарных деревьев поиска и операций над ними. Объектом исследования является бинарное дерево поиска. Предметом исследования является набор алгоритмом для работы с бинарными деревьями поиска.
1. Теоретическая часть
Бинарные деревья Дерево - в информатике и программировании одна из самых распространенных структур данных. Формально дерево определяется как конечное множество Т с одной или более вершин (узлов, nodes), которое удовлетворяет следующим требованиям: существует один выделенный узел - корень (root) дерева, другие узлы (исключая корня) распределены среди m ? 0 непересекающихся множеств T1. Tm и каждая из этих множеств в свою очередь является деревом. Деревья T1. Tm называют поддеревьев (subtrees) данного корня. Из этого определения следует, что каждая вершина является в свою очередь корнем некоторого поддерева. Количество поддеревьев вершины называется степени (degree) этой вершины. Вершина степени нуль называется конечной (terminal) или листом (leaf). Неконечной вершина также называется вершина ветвления (branch node). Пусть x - произвольная вершина дерева с корнем r. Тогда существует единственный путь из r в x. Все вершины на этом пути называются предками (ancestors) x; если некоторая вершина y является предком x, то x называется потомком (descendant) y. Потомки и предки вершины x, не совпадают с ней самой, называются собственными потомками и предками. Каждую вершину x, в свою очередь, можно рассматривать как корень некоторого поддерева, элементами которого являются вершины-потомки x. Если вершины x является предком y и не существует вершин между ними (т.е. x и y соединены одним ребром), а также существуют предки для x (т.е. x не является корнем), то вершина x называется отцом (parent) к y, а y - ребенком (child) x. Корневая вершина единственная, которая не имеет родителей. Вершины, имеющие общего отца, называются братьями (siblings). Вершины, имеющие детей, называются внутренними (internal). Глубиной вершины x называется длина пути от корня к этой вершине. Максимальная глубина вершин дерева называется высотой. Если существует относительный порядок на деревьями T1. Tm, то такое дерево называется упорядоченным (ordered tree) или плоским (plane tree). Лесом (forest) называют множество деревьев, которые не пересекаются. Чаще всего дерева в информатике изображают с корнем, который находится сверху (говорят, что дерево в информатике "растет вниз"). Важным частным случаем корневых деревьев являются бинарные деревья, которые широко применяются в программировании и определяются как множество вершин, которое имеет выделенный корень и два поддерева (правое и левое), не пересекаются, либо являются пустой множеством вершин (в отличие от обычного дерева, не может быть пустым). Важными операциями на деревьях являются: обход вершин в разном порядке: 1. перенумерация вершин, 2. поиск элемента, 3. добавления элемента в определенное место в дереве, 4. удаления элемента, 5. удаления целого фрагмента дерева, 6. добавления целого фрагмента дерева, 7. трансформации (повороты) фрагментов дерева, нахождение корня для любой вершины. Наибольшее распространение эти структуры данных получили в тех задачах, где необходимо манипулирования с иерархическими данными, эффективный поиск в данных, их структурированное хранение и модификация. В программировании бинарное дерево - дерево структура данных, в котором каждая вершина имеет не более двух детей. Обычно такие дети называются правым и левым. На базе бинарных деревьев строятся такие структуры, как бинарные деревья поиска и бинарные вместе. Идеальное бинарное дерево - это такое полное бинарное дерево, в котором листья (вершины без детей) лежат на одинаковой глубине (расстояния от корня). Бинарное дерево на каждом n-ом уровне имеет от 1 до 2n вершин. Обход бинарного дерева Часто возникает необходимость обойти все вершины дерева для анализа информации, в них находится. Существуют несколько порядков такого обхода, каждый из которых имеет определенные свойства, важные в тех или иных алгоритмах: прямой (preorder), центрированный (inorder) и обратной (postorder). Реализация бинарного дерева Каждая вершина содержит указатели на правую и левую ветвь ребенка (left и right). Есть несколько вариантов конструирования бинарных деревьев в зависимости от задач, которые решаются этими структурами и возможностей того или иного языка программирования. Реализация с использованием указателей предусматривает хранение в каждой вершине дерева x вместе с данными двух полей с указателями (правым и левым) right [x] и left [x] на соответствующих детей этой вершины. Модифицированная реализация бинарного дерева Каждая вершина содержит также указатель на родительскую вершину. Также иногда добавляется указатель p [x] на родительскую вершину. Это оказывается полезным, когда необходим быстрый доступ к родительской вершины и упрощает некоторые алгоритмы. Иногда достаточно только указателя на родительскую вершину. Вообще любое ориентированное дерево можно описать, зная только связи от детей до родительской вершины. Некоторые разновидности бинарных деревьев (например, красно-черные деревья или AVL-дерева), требуют сохранения в вершинах и некоторой дополнительной информации. Если у вершины отсутствует один или оба ребенка, соответствующие указатели инициализируются специальными пустыми значениями. Представление n-арных деревьев как бинарных Существует единственное и взаимооднозначное отображение произвольного упорядоченного дерева в бинарное. Для этого следует последовательно связать всех детей каждой семьи с первым ребенком и и удалить все вертикальные соединения исключением соединения отца с первым ребенком в семье. То есть каждая вершина N упорядоченного n-арного дерева соответствует вершине M некоторого бинарного дерева. Левый ребенок вершины M соответствует первому ребенку вершины N, а чтобы ребенок M соответствует первому из следующих братьев N (то есть первом из следующих детей отца вершины N). Такое соответствие называется естественной соответствия между n-арным и бинарным деревом. Бинарное дерево поиска в информатике - бинарное дерево, в котором каждой вершине x сопоставлено определенное значение val [x]. При этом такие значения должны удовлетворять условию упорядоченности: пусть x - произвольная вершина бинарного дерева поиска. Если вершина y находится в левом поддереве вершины x, то val [y] ? val [x]. Такое структурирование позволяет напечатать все значения в возрастающем порядке с помощью простого алгоритма центрированного обхода дерева. Поиск в бинарном дереве...
2. Практическая часть
2.1 Описание и пример работы алгоритма
Пусть высота бинарного дерева равна h. Тогда алгоритм поиска элемента k в дереве с корнем x выполняется за время O(h): Tree_Search(x, k) 1 if x = NIL | k = key[x] 2 then return x 3 if k ‹ key[x] 4 then return T ree_Search(left[x], k) 5 else return T ree_Search(right[x], k) Процедуру можно превратить в итеративную с помощью хвостовой рекурсии. Обход дерева Поиск элемента в дереве является частным случаем процедуры обхода дерева. Существует несколько принципиально разных способов обхода: 1. Обход в прямом порядке, когда каждый узел посещается до того, как посещены его потомки (prefix traverse). Для корня дерева рекурсивно вызывается следующая процедура: (a) Посетить узел. (b) Обойти левое поддерево. (c) Обойти правое поддерево. Такой обход используется, например, в решение задачи методом деления на части и в стратегии “разделяй и властвуй” (сортировка слиянием, быстрая сортировка, одновременное нахождение макси- мума и минимума последовательности чисел, умножение длинных чисел и т.д.). 2. Симметричный обход, когда сначала посещается левое поддерево, затем узел, затем правое поддерево (infix traverse). Для корня дерева рекурсивно вызывается следующая процедура: (a) Обойти левое поддерево. (b) Посетить узел. (c) Обойти правое поддерево. 3. Обход в обратном порядке (postfix traverse), когда узлы посещаются “снизу вверх” по следующей процедуре: (a) Обойти левое поддерево. (b) Обойти правое поддерево. (c) Посетить узел. Такой обход используется в анализе игр с полной информацией, в динамическом программировании и для вычисления выражений в постфиксной форме. Все три варианта обхода в глубину можно реализовать итеративно. Для бинарных и для произвольных (N -арных деревьев) существует обход в ширину, когда узлы посещаются уровень за уровнем (k-й уровень дерева – множество узлов с высотой k). Каждый уровень обходится слева направо. Для его реализации используется структура queue (очередь). Вставка и удаление элемента Алгоритм вставки узла z, у которого key[z] = v, left[z] = NIL, right[z] = NIL в бинарное дерево T : Tree_Insert(T , z) 1 y ‹ NIL 2 x ‹ root[T ] 3 while x ?= NIL 4 do y ‹ x 5 if key[z] ‹ key[x] 6 then x ‹ left[x] 7 else x ‹ right[x] 8 p[z] ‹ y 9 if y = NIL 10 then root[T ] ‹ z //Дерево T – пустое 11 else if key[z] ‹ key[y] 12 then left[y] ‹ z 13 else right[y] ‹ z Цикл в начале процедуры перемещает указатели вниз по дереву в зависимости от сравнения ключей key[x] и key[z], до тех пор, пока x не станет равным NIL. Это значение находится именно в той позиции, куда следует вставить узел z. Процедура Tree_Delete рассматривает три возможных случая: 1. Если у узла z нет дочерних узлов, он просто удаляется из дерева. 2. Если у узла один дочерний узел, он “склеивается” с родительским для z. 3. Если дочерних узла два, то в дереве находим следующий за z узел y, у которого нет левого дочернего узла, убираем его из позиции, где он находился ранее и заменяем им узел z. Можно показать, что если у узла BST два дочерних узла, то у пред- шествующего узла нет правого дочернего, а у последующего – левого. Если в дереве T существуют два узла a и b, a ‹ b, такие, что rank(a) = k, rank(b) = k + 1. Т.е. узел b является последующим за a. Тогда левым дочерним узлом узла b может являться только элемент x ‹ b. Но из условия предшествия следует, что x ‹ a и rank(x) ‹ rank(a). Т.к. узлы a и b уже размещены в дереве, алгоритм Tree_Insert поместит x в левое поддерево элемента a, но не b. Процедура Tree_Successor возвращает следующий элемент за аргу- ментом в отсортированной последовательности. Tree_Delete(T, z) 1 if left[z] = NIL | right[z] = NIL 2 then y ‹ z 3 else y ‹ T ree_Successor(z) 4 if left[y] ?= NIL 5 then x ‹ left[y] 6 else x ‹ right[y] 7 if x ?= NIL 8 then p[x] ‹ p[y] 9 if p[y] = NIL 10 then root[T ] ‹ x 11 else if y = left[p[y]] 12 then left[p[y]] ‹ x 13 else right[p[y]] ‹ x 14 if y ?= z 15 then key[z] ‹ key[y] 16 //Копирование сопутствующих данных в z 17 return y Очевидно, что балансировку дерева можно нарушить, вставляя или удаляя специально подобранные элементы. Для борьбы с таким поведением существуют специальные структуры данных и соответствующие алгоритмы: красно-чёрные деревья, AVL-деревья, декартовы деревья (Treap) и т.п.
2.4 Исследование алгоритма и его эмпирический анализ
Бинарные деревья поиска гораздо эффективнее в операциях поиска, чем линейные структуры, в которых затраты времени на поиск пропорциональны O (n), где n - размер массива данных, тогда как в полном бинарном дереве это время пропорционален в среднем O (log2n) или O ( h), где h - высота дерева (хотя гарантировать, что h не превышает log2n можно только для сбалансированных деревьев, которые являются эффективными на поисковых алгоритмах.).
Выводы
Для решения проблемы излишних затрат на вставку и удаления и сохранения быстрого бинарного поиска используется явная древовидная структура – дерево бинарного поиска (BST). BST – это бинарное дерево, с каждым из узлов которого связан ключ, причем ключ в любом узле больше(или равен) ключам во всех узлах левого поддерева этого узла и меньше(или равен) ключам во всех узлах правого поддерева этого узла. Каждый узел BST содержит ссылки на левого и правого сына, возможно на родителя, ключ и ссылку на данные. Ввиду рекурсивной природы дерева обычно алгоритмы операций также рекурсивны. Производительность операций вставки, поиска и удаления в среднем пропорциональна О(log n). Но BST-дерево в худшем случае вырождается(когда ключи поступают в дерево в порядке возрастания или убывания). В этом случае сложность операций оценивается как О(n).
Литература
1. Автоматическое построение ассоциативного списка со сжатием информации. - М., 1976. 2. Ахо, Альфред В. и др. Построение и анализ вычислительных алгоритмов. - М .: Мир, 1979 3. Баррон Д. Рекурсивные методы в программировании, - М .: 1974 4. Барашенков В.В. Анализ и преобразование операторных схем алгоритмов: учебное пособие. - Л .: ЛЭТИ, 1979. 5. Барашенков В.В. Интерпретация операторных схем алгоритмов. - Л .: ЛЭТИ, 1978. 6. Бентли Дж. Жемчужины творчества программистов. - М .: Мир, 1990. 7. Дмитриева М.В., Кубенский А.А. Элементы современного программирования - СПб .: 1991. 8. Квиттнер П. Задачи, программы, вычисления, результаты. - М .: Мир, 1980. 9. Кинг Д. Создание еффективно программного обеспечения. - М .: Мир, 1991. 10. Криницкий Н.А. Программирование и алгоритмические языки. - 1975. 11. Малоземова В.Н. Певный А.Б. Рекуррентные вычисления. - Л., изд. ун-та, 1976. 12. Прикладные вопросы системного анализа. Межвузовский тематический сборник. Вып.2. Куйбышев, 1976. 13. Шауман А.М. Основы машинной арифметики. - 1979.
* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.
