Автор24

Информация о работе

Подробнее о работе

Страница работы

АМОРТИЗИРОВАННЫЕ СБАЛАНСИРОВАННЫЕ ПО ВЕСУ ДЕРЕВЬЯ

  • 31 страниц
  • 2016 год
  • 174 просмотра
  • 0 покупок
Автор работы

Crazy55

700 ₽

Работа будет доступна в твоём личном кабинете после покупки

Гарантия сервиса Автор24

Уникальность не ниже 50%

Фрагменты работ

Введение 3
Глава 1. Деревья со штрафами 4
1.1. Представление графа 4
1.2. Понятие бинарного дерева 4
1.3. Деревья со штрафами 6
1.4. Структура данных 7
1.5. Операции 8
1.5.1. Поиск 8
1.5.2. Вставка 8
1.5.3. Удаление 8
1.6. Выводы по 1 главе 9
Глава 2. Реализация алгоритма построения дерева со штрафами 10
2.1. Выбор языка программирования. 10
2.2. Создание приложения «Scapegoat-дерево» 10
2.2.1. Класс «SGTNode»: 10
2.2.2. Класс «ScapeGoatTree»: 11
2.2.3. Функции вставки 12
2.2.4. Функции перестройки дерева 14
2.2.5. Функции удаления узла 15
2.2.6. Функция удаления дерева 16
2.2.7. Функции вывода дерева (по порядку) 16
2.2.8. Функция поиска элемента в дереве 16
2.2.9. Функция подсчета узлов 16
2.3. Работа программы 16
2.4. Выводы по 2 главе 19
Заключение 20
Литература 21

1.2. Понятие бинарного дерева
Граф без циклов называют ациклическим. Дерево – это связный ациклический граф [2, c. 130].
Бинарное (двоичное) дерево - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла [5, c. 1].
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом[5, c. 1].
Пример бинарного дерева представлен на рисунке 2.


Рис. 2 - Схематичное изображение бинарного дерева

Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.
...

1.4. Структура данных
В этом разделе будут описаны атрибуты дерева со штрафами. В основном, дерево со штрафами состоит из обычного двоичного дерева поиска, с двумя дополнительными значениями, хранящимися в корне.
Каждый узел х из дерева поддерживает следующие атрибуты:
• T — так будем обозначать дерево
• Value[x] — значение хранится в узле х.
• parent[x] —родитель вершины х
• left[x] — левый «сын» вершины х
• right[x] — правый «сын» вершины х
• brother(x) — брат вершины х
• n(T) — глубина дерева T. Это глубина самой глубокой вершины дерева T
• Коэффициент α — это число в диапазоне от [0.5; 1), определяющее требуемую степень качества балансировки дерева. Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен α * size(x) и вес ей правого сына меньше либо равен α * size(x)
[7, c.165]
Дерево T в целом имеет следующие атрибуты:
• root [T] – указатель на корневой узел дерева.
...

2.1. Выбор языка программирования.
Для написания программы будет использоваться язык программирования высокого уровня. А именно язык C++ среды разработки Microsoft Visual Studio 2013, за счет нижеперечисленным возможностям.
С++ – это чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения. Поддержка различных стилей программирования: традиционное императивное программирование (структурное, объектно-ориентированное), обобщённое программирование, функциональное программирование, порождающее мета программирование. Доступность. Для. С++ существует огромное количество учебной литературы, переведённой на всевозможные языки. Язык имеет низкий порог вхождения, но среди всех языков такого рода обладает наиболее широкими возможностями.

2.2.
...

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

2.2.4. Функции перестройки дерева
Есть много способов восстановления поддерева с корнем в узле U, в идеально сбалансированное дерево. Один из самых простых является прохождение u поддерева, собрав все свои узлы в массив mas, затем рекурсивно построить сбалансированное поддерево использую mas. Если предположить что
m=length(mas)/2, то элемент mas[m] станет корнем нового поддерева, mas[0],…, mas[m-1] рекурсивно откладываются в левом поддереве и mas[m+1],…, mas[length(mas)-1] рекурсивно откладываются в правом поддереве.
Вызов rebuild(u) занимает O(size(u)) времени. Полученное поддерево имеет минимальную высоту: нет дерева меньшей высоты, которое имеет size(u) узлов.
...

2.2.5.
...

1. Окулов С. М. Программирование в алгоритмах Издательство «БИНОМ. Лаборатория знаний» 2002.
2. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике [Электронный ресурс] : учебное пособие / С. М. Окулов. – 2-е изд. (эл.). – М. : БИНОМ. Лаборатория знаний, 2012. – 422 с.
3. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = IntroductiontoAlgorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. —1229 с.
4. Майкл Ласло Вычислительная геометрия и компьютерная графика на С++ – М.: Бином, 1997. - 301 с.
5. Роман Акопов. Двоичные деревья поиска. RSDN Magazine #5-2003 (13.03.2005)
6. В.И. Носов, Т.В. Бернштейн, Н.В. Носкова, Т.В.Храмова. Элементы тео- рии графов. Учебное пособие. — Новосибирск, 2008. — 107с
7. Гальперин, Игаль; Ривест, Рональд Л. (1993). "Scapegoat деревья" .

Форма заказа новой работы

Не подошла эта работа?

Закажи новую работу, сделанную по твоим требованиям

Согласен с условиями политики конфиденциальности и  пользовательского соглашения

Фрагменты работ

Введение 3
Глава 1. Деревья со штрафами 4
1.1. Представление графа 4
1.2. Понятие бинарного дерева 4
1.3. Деревья со штрафами 6
1.4. Структура данных 7
1.5. Операции 8
1.5.1. Поиск 8
1.5.2. Вставка 8
1.5.3. Удаление 8
1.6. Выводы по 1 главе 9
Глава 2. Реализация алгоритма построения дерева со штрафами 10
2.1. Выбор языка программирования. 10
2.2. Создание приложения «Scapegoat-дерево» 10
2.2.1. Класс «SGTNode»: 10
2.2.2. Класс «ScapeGoatTree»: 11
2.2.3. Функции вставки 12
2.2.4. Функции перестройки дерева 14
2.2.5. Функции удаления узла 15
2.2.6. Функция удаления дерева 16
2.2.7. Функции вывода дерева (по порядку) 16
2.2.8. Функция поиска элемента в дереве 16
2.2.9. Функция подсчета узлов 16
2.3. Работа программы 16
2.4. Выводы по 2 главе 19
Заключение 20
Литература 21

1.2. Понятие бинарного дерева
Граф без циклов называют ациклическим. Дерево – это связный ациклический граф [2, c. 130].
Бинарное (двоичное) дерево - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла [5, c. 1].
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом[5, c. 1].
Пример бинарного дерева представлен на рисунке 2.


Рис. 2 - Схематичное изображение бинарного дерева

Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.
...

1.4. Структура данных
В этом разделе будут описаны атрибуты дерева со штрафами. В основном, дерево со штрафами состоит из обычного двоичного дерева поиска, с двумя дополнительными значениями, хранящимися в корне.
Каждый узел х из дерева поддерживает следующие атрибуты:
• T — так будем обозначать дерево
• Value[x] — значение хранится в узле х.
• parent[x] —родитель вершины х
• left[x] — левый «сын» вершины х
• right[x] — правый «сын» вершины х
• brother(x) — брат вершины х
• n(T) — глубина дерева T. Это глубина самой глубокой вершины дерева T
• Коэффициент α — это число в диапазоне от [0.5; 1), определяющее требуемую степень качества балансировки дерева. Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен α * size(x) и вес ей правого сына меньше либо равен α * size(x)
[7, c.165]
Дерево T в целом имеет следующие атрибуты:
• root [T] – указатель на корневой узел дерева.
...

2.1. Выбор языка программирования.
Для написания программы будет использоваться язык программирования высокого уровня. А именно язык C++ среды разработки Microsoft Visual Studio 2013, за счет нижеперечисленным возможностям.
С++ – это чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения. Поддержка различных стилей программирования: традиционное императивное программирование (структурное, объектно-ориентированное), обобщённое программирование, функциональное программирование, порождающее мета программирование. Доступность. Для. С++ существует огромное количество учебной литературы, переведённой на всевозможные языки. Язык имеет низкий порог вхождения, но среди всех языков такого рода обладает наиболее широкими возможностями.

2.2.
...

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

2.2.4. Функции перестройки дерева
Есть много способов восстановления поддерева с корнем в узле U, в идеально сбалансированное дерево. Один из самых простых является прохождение u поддерева, собрав все свои узлы в массив mas, затем рекурсивно построить сбалансированное поддерево использую mas. Если предположить что
m=length(mas)/2, то элемент mas[m] станет корнем нового поддерева, mas[0],…, mas[m-1] рекурсивно откладываются в левом поддереве и mas[m+1],…, mas[length(mas)-1] рекурсивно откладываются в правом поддереве.
Вызов rebuild(u) занимает O(size(u)) времени. Полученное поддерево имеет минимальную высоту: нет дерева меньшей высоты, которое имеет size(u) узлов.
...

2.2.5.
...

1. Окулов С. М. Программирование в алгоритмах Издательство «БИНОМ. Лаборатория знаний» 2002.
2. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике [Электронный ресурс] : учебное пособие / С. М. Окулов. – 2-е изд. (эл.). – М. : БИНОМ. Лаборатория знаний, 2012. – 422 с.
3. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = IntroductiontoAlgorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. —1229 с.
4. Майкл Ласло Вычислительная геометрия и компьютерная графика на С++ – М.: Бином, 1997. - 301 с.
5. Роман Акопов. Двоичные деревья поиска. RSDN Magazine #5-2003 (13.03.2005)
6. В.И. Носов, Т.В. Бернштейн, Н.В. Носкова, Т.В.Храмова. Элементы тео- рии графов. Учебное пособие. — Новосибирск, 2008. — 107с
7. Гальперин, Игаль; Ривест, Рональд Л. (1993). "Scapegoat деревья" .

Купить эту работу

АМОРТИЗИРОВАННЫЕ СБАЛАНСИРОВАННЫЕ ПО ВЕСУ ДЕРЕВЬЯ

700 ₽

или заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 500 ₽

Гарантии Автор24

Изображения работ

Страница работы
Страница работы
Страница работы

Понравилась эта работа?

или

7 апреля 2017 заказчик разместил работу

Выбранный эксперт:

Автор работы
Crazy55
4.9
Купить эту работу vs Заказать новую
0 раз Куплено Выполняется индивидуально
Не менее 40%
Исполнитель, загружая работу в «Банк готовых работ» подтверждает, что уровень оригинальности работы составляет не менее 40%
Уникальность Выполняется индивидуально
Сразу в личном кабинете Доступность Срок 1—6 дней
700 ₽ Цена от 500 ₽

5 Похожих работ

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

Создание базы данных для автоматизации процесса управления кадрами на предприятии

Уникальность: от 40%
Доступность: сразу
1000 ₽
Курсовая работа

Оптимизация сайта при помощи методов ИИ для увеличения конверсионного действия

Уникальность: от 40%
Доступность: сразу
300 ₽
Курсовая работа

Сравнение операционных систем Linux, Windows и MacOS

Уникальность: от 40%
Доступность: сразу
400 ₽
Курсовая работа

Разработка программы обработки списка смартфонов

Уникальность: от 40%
Доступность: сразу
350 ₽
Курсовая работа

Решение задач многомерной оптимизации. Методы безусловной оптимизации. Поиск условного экстремума, используя квадратичный штраф. (MathCad, Python).

Уникальность: от 40%
Доступность: сразу
1000 ₽

Отзывы студентов

Отзыв Далиас об авторе Crazy55 2018-05-11
Курсовая работа

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

Общая оценка 5
Отзыв pocya об авторе Crazy55 2016-04-07
Курсовая работа

Спасибо за работу!

Общая оценка 5
Отзыв Марина [email protected] об авторе Crazy55 2015-08-25
Курсовая работа

все отлично, спасибо!

Общая оценка 5
Отзыв Татьяна_5085 об авторе Crazy55 2016-09-15
Курсовая работа

Все ОК

Общая оценка 5

другие учебные работы по предмету

Готовая работа

Адаптация программных систем на основе функционального подхода

Уникальность: от 40%
Доступность: сразу
150 ₽
Готовая работа

Экспертная кибернетическая идентификация

Уникальность: от 40%
Доступность: сразу
140 ₽
Готовая работа

Моя будущая профессия – программист

Уникальность: от 40%
Доступность: сразу
875 ₽
Готовая работа

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

Уникальность: от 40%
Доступность: сразу
150 ₽
Готовая работа

Состав языка программирования. Типы данных.

Уникальность: от 40%
Доступность: сразу
100 ₽
Готовая работа

Базовые алгоритмические конструкции структурного программирования

Уникальность: от 40%
Доступность: сразу
100 ₽
Готовая работа

основы объектно-ориентированного программирования

Уникальность: от 40%
Доступность: сразу
130 ₽
Готовая работа

Экзамен по VBA Составить программу вычисления суммы значений функции, меньших единицы и суммы Z значений функции, больших единицы = ln(2 + ко

Уникальность: от 40%
Доступность: сразу
67 ₽
Готовая работа

Пользовательские типы данных

Уникальность: от 40%
Доступность: сразу
120 ₽
Готовая работа

Алгоритмизация ввода-вывода данных

Уникальность: от 40%
Доступность: сразу
120 ₽
Готовая работа

Функции как законченные алгоритмические конструкции

Уникальность: от 40%
Доступность: сразу
120 ₽
Готовая работа

Указатели и массивы

Уникальность: от 40%
Доступность: сразу
120 ₽