Исследование сбалансированных деревьев

Закрытое Акционерное Общество

<< Азербайджан Хава Йоллары >>

Национальная Академия Авиации

Факультет:  Аэрокосмический

Кафедра:   << Аэрокосмические информационные системы >>

Специальность:  050655 - Информационные технологии

Дисциплина:   << Структура данных и алгоритмов >>

КУРСОВАЯ РАБОТА

Тема: Исследование сбалансированных деревьев

Заведующий кафедрой: д.ф.н.,доцент. Габибуллаев.С.Б

Руководитель темы: д.ф.н., доцент. Габибуллаев.С.Б

Студент: Агаева Ульвия             гр.1446-r

Баку-2017

ЗАО << Азербайджан Хава Йоллары >>

Национальная Академия Авиации

КАФЕДРА << Аэрокосмические информационные системы >>

Курсовая работа

Задание

Предмет:  Структура данных и алгоритмов

Курс ll___Группа__1446r_Агаева Ульвия

1.Тема курсовой работы: Исследование сбалансированных деревьев

2.Дата выдачи задания: 

3.Исходные данные к курсовой работе: 1. Поиск двоичного дерева 1.1. Поиск узла в двоичном дереве 1.2 Вставка узла в двоичное дерево  1.3 Удаление узла из двоичного дерева  2. АВЛ-деревья 2.1 Вставка узла в АВЛ-дерево 2.2 Удаление узла из АВЛ-дерева

4.Содержание пояснительной записки:

5.Перечень графического материала:

6.Литература:

Заведующий кафедрой_____________Габибуллаев.С.Б.

Преподаватель______________Габибуллаев.С.Б.

Студент_____________Агаева Ульвия.

Дата защиты проекта <<____>> ______________2017  Оценка _________

Комиссия защиты ___________________________________________

____________________________________________

____________________________________________

Cодержание

 Введение ......................................................................................4

1. Поиск двоичного деревья .....................................................5

1.1 Поиск узла в двоичном дереве ...........................................6

1.2 Вставка узла в двоичное дерево.........................................7

1.3 Удаление узла из двоичного дерева...................................9

2. АВЛ-деревья….………………………………………...…...11

2.1  Вставка узла в АВЛ-дерево ………...……..….......……..13

2.2 Удаление узла из АВЛ-дерева…………………………...20

Заключение…………………………………………………….24

Литература……………………………………………………..25

Введение

Данное методическое пособие посвящено определенному виду структур данных – сбалансированным деревьям поиска. В начале пособия вводится понятие дерева поиска, на примерах рассматриваются его свойства, разбираются основные операции над ним: поиск, вставка и удаление узла. Далее подробно излагается теоретический материал по трем видам сбалансированных деревьев поиска: АВЛ-деревьям. Основные операции над этими деревьями рассматриваются по шагам, с комментариями и иллюстрациями. Приводятся оценки сложности операций с доказательствами. Приводится описание реализации этих операций на псевдокоде. Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы. В этой главе будет рассматриваться другая разновидность бинарных поисковых деревьев - AVL-деревья или сбалансированные двоичные деревья с минимальным временем поиска по дереву. Это свойство AVL-деревьев обеспечивается их сбалансированностью, которая одновременно усложняет алгоритмы для вставки узлов в дерево и их последующего удаления.