Курсовая работа: Исследование деревьев бинарного поиска

Оглавление

Введение. 3
1 Динамические структуры данных. 5
1.1 Введение в динамические структуры данных. 5
1.2 Классификация динамических структур данных. Бинарные деревья. 7
Глава 2. Операции над бинарным деревом.. 11
2.1 Узел бинарного дерева. 11
2.2 Обход бинарного дерева. 11
2.3 Упорядоченные деревья. Включение нового узла, поиск по дереву с включением.. 14
2.4 Упорядоченные деревья. Поиск заданного значения. 17
2.5 Удаление бинарного дерева. 18
2.6 Удаление узла из упорядоченного дерева. 19
2.7 Пример использования упорядоченного бинарного дерева для частотного анализа данных. 21
Заключение. 25
Список использованных источников. 27

Введение

Актуальность выбранной темы состоит в том, что структуры данных и алгоритмы являются теми материалами, из которых создается программное обеспечение.
Очень часто при разработке приложений, работающих с большим объемом входных данных, возникает вопрос об их сохранении в процессе выполнения программы. Несомненно, массив данных решает проблему хранения данных, но очевидно, что он не лишен недостатков. Самое главное, конечно, фиксированный размер. Это свойство нельзя изменить даже для динамически создаваемых массивов, поэтому выделять им память нужно «с запасом». Однако «запас» тоже ограничен и никто не может гарантировать, что его будет достаточно, иначе этого «запаса» может хватить так, что большая часть памяти, выделенной программе, будет потрачена впустую.
Эта проблема решается с помощью динамических структур данных.
Динамические переменные создаются в динамической памяти во время выполнения программы. Доступ к ним осуществляется через указатели. Используя эти переменные, вы можете обрабатывать данные, неизвестные до запуска программы. Память для таких данных выделяется блоками, взаимодействующими друг с другом. Такой способ хранения данных называется динамическими структурами.
Деревья — известные нелинейные конструкции. Они не хранят данные линейно, а организуют их иерархически. Деревья — очень удобный инструмент для представления информации разного рода.
Деревья отличаются от простых графов тем, что при обходе дерева невозможно зацикливаться. Это делает графики очень удобной формой организации данных для различных алгоритмов. Так, понятие дерева активно используется в информатике и программировании при изучении динамических структур данных.
Объект исследования – структуры данных.
Предмет исследования – бинарные деревья.
Цель исследования заключается в изучении динамических структур данных, а именно – бинарных деревьев.
Задачи исследования формируются исходя из его цели и заключаются в следующем:

• рассмотреть динамические структуры данных;
• рассмотреть операции над бинарным деревом.