Очень доброжелательный и компетентный автор. Всегда был на связи, все разъяснил, предоставил несколько вариантов программы. Рекомендую.
Информация о работе
Подробнее о работе
АМОРТИЗИРОВАННЫЕ СБАЛАНСИРОВАННЫЕ ПО ВЕСУ ДЕРЕВЬЯ
- 31 страниц
- 2016 год
- 174 просмотра
- 0 покупок
Гарантия сервиса Автор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 деревья" .
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
