СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕРЕВЬЕВ ПОИСКА И СОЗДАНИЕ ОБУЧАЮЩЕЙ СИСТЕМЫ ПО ИХ ПОСТРОЕНИЮ

Аннотация 2
ВВЕДЕНИЕ 6
1 ПОСТАНОВКА ЗАДАЧИ 9
2 ПРЕДМЕТНАЯ ОБЛАСТЬ 10
2.1 ДВОИЧНОЕ ДЕРЕВО ПОИСКА 10
2.2. СБАЛАНСИРОВАННОЕ ДЕРЕВО 11
2.2.1 ОПРЕДЕЛЕНИЕ СБАЛАНСИРОВАННОГО ДЕРЕВА 11
2.2.2 БАЛАНСИРОВКА 12
2.2.3 АЛГОРИТМ ДОБАВЛЕНИЯ ВЕРШИНЫ В АВЛ-ДЕРЕВО 13
2.3 В-ДЕРЕВО 14
2.3.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА В-ДЕРЕВА 14
2.3.2 ДОБАВЛЕНИЕ КЛЮЧА В В-ДЕРЕВО 15
2.4 КРАСНО - ЧЕРНОЕ ДЕРЕВО 16
2.4.1 ОПРЕДЕЛЕНИЕ И СВОЙСТВА КРАСНО - ЧЕРНОГО ДЕРЕВА 16
2.4.2 СЛУЧАИ ПРИ ВСТАВКЕ КЛЮЧА В ДЕРЕВО 18
2.5 ДЕРЕВО ВАН ЭМДЕ БОАСА 20
2.5.1 ОПРЕДЕЛЕНИЕИ СВОЙСТВА ДЕРЕВА ВАН ЭМДЕ БОАСА 20
2.5.2 ПРОТОСТРУКТУРА ДЕРЕВА ВАН ЭМДЕ БОАСА 21
2.5.3 ДЕРЕВО ВАН ЭМДЕ БОАСА 24
2.5.4 ОПЕРАЦИИ ДЕРЕВА ВАН ЭМДЕ БОАСА 26
2.6 РАНДОМИЗИРОВАННОЕ ДЕРЕВО 27
2.6.1 ОПРЕДЕЛЕНИЕ РАНДОМИЗИРОВАННОГО ДЕРЕВА 27
2.6.2 ВСТАВКА УЗЛА В РАНДОМИЗИРОВАННОЕ ДЕРЕВО 28
2.7 ДЕКАРТОВОЕ ДЕРЕВО 29
2.7.1 ОПРЕДЕЛЕНИЕ ДЕКАРТОВОГО ДЕРЕВА 29
2.7.2 ПОЧЕМУ ДЕРЕВО НАЗЫВАЕТСЯ ДЕКАРТОВЫМ? 30
2.7.3 ОПЕРАЦИИ СЛОЖЕНИЯ И ДЕЛЕНИЯ 30
2.7.4 ОПЕРАЦИИ ВСТАВКИ И УДАЛЕНИЯ УЗЛА 32
2.8 ПРИМЕНЕНИЕ ДЕРЕВЬЕВ ПОИСКА 33
3 ОПИСАНИЕ ОБУЧАЮЩЕЙ СИСТЕМЫ 36
4 СЛОЖНОСТЬ ОПЕРАЦИЙ 46
5 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДЕРЕВЬЕВ ПОИСКА 47
ЗАКЛЮЧЕНИЕ 52
ЛИТЕРАТУРА 53
ПРИЛОЖЕНИЕ А 55
ПРИЛОЖЕНИЕ Б 58

Купить

Историю технологии баз данных принято отсчитывать с начала 1960-х гг., когда появились первые попытки создания специальных программных средств управления базами данных. За прошедшие десятилетия возникали и использовались различные подходы к их организации. Для создания баз данных и работы с ними использовались файлы. Данные хранились в виде списков. Характер обработки определялся всеобщим использованием в качестве носителя магнитной ленты.
Период с 1968г. по 1980г. считают эрой обработки не реляционных баз данных. Сначала была разработана иерархическая модель данных. А затем появилась сетевая модель данных.
С 1980г. по настоящее время - период реляционной модели данных.
С распространением интернета в середине 90-х годов повысилось значение и важность технологии баз данных. Ранние статические веб-страницы уступили дорогу динамическим, в результате чего большие организации начали использовать интернет для публикации своих данных.
Хранение данных не существовало бы без структуры. Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Одним из представителей структуры данных является дерево поиска. Существуют различные деревья поиска. Некоторые из них приведены далее:
• АВЛ-дерево. Предложено в 1962 году Адельсоном-Вельским Георгием Максимовичем и Ландасом Евгением Михайловичем.
• 2-3 деревья. Предложено Д.Э. Хопкрофтом в 1970 году.
• В-дерево. Предложено в 1970 году Рудольфом Байером и Мак-Крейтом.
• Красно-черное дерево. Предложено в 1972 году Рудольфом Байером под названием «симметричные бинарные В-деревья». Название «красно¬черное дерево» структура данных получила в 1978 году в статье Л.Гимпаса и Р.Седжвика.
• Дерево ван Эмде Боаса. Предложено в 1975 году.
•Рандомизированное дерево. Основателем считается Майкл О.Рабин, исследовавший рандомизированный тест простоты чисел в 1977 году.
• Декартово дерево. Предложено в 1996 году Раймундом Сейделем и Сецилией Арагон.
Цель создания деревьев поиска - это быстрый поиск информации в больших базах данных, например таких, как телефонные справочники в сотовых компаниях. С ростом числа пользователей база увеличивается. Существуют компании свыше миллиона пользователей. Деревья поиска позволяют значительно сократить время поиска необходимого элемента в базе данных.
Каждое дерево поиска имеет свои преимущества и недостатки. Поэтому для оптимального выбора древовидной структуры при разработке базы данных следует изучить все возможные деревья. Главной задачей данной работы стало изучение свойств деревьев поиска, а также проведения сравнительного анализа этих свойств.
В настоящее время роль информационных технологий очень важна . Поэтому возникает необходимость создания обучающих систем. Но в нынешнем разнообразии систем нет эффективных программ для изучения деревьев поиска. А эти структуры данных очень важны для хранения и быстрого поиска информации в базах данных и других поисковых системах. Так как обучающие системы служат хорошим помощником для изучения необходимой информации, второй задачей работы стало создание обучающей системы для изучения деревьев поиска и проверке полученных знаний.
Обучающая система - это программное средство, предназначенное для решения определенных педагогических задач, имеющее предметное содержание и ориентированное на взаимодействие с обучаемым. Такая система должна содержать учебный материал по определенной предметной области. Под учебным материалом понимается информация как декларативного (описательного, иллюстрационного) характера, так и задания для контроля знаний и умений, а также модели и алгоритмы, представляющие обучаемые объекты и процессы.
Из всего вышеперечисленного следует цель данной работы - провести сравнительный анализ деревьев поиска и создать эффективную обучающую систему, ориентированную на изучение деревьев поиска.

Купить