Алгоритмы и структуры данныхЛабораторная работаТУСУР
Лабораторная работа посвящена изучению структуры данных «бинарное дерево» и получению практических навыков создания таких структур и применения алгоритмов их обработки. В работе рассматривается классическое бинарное дерево поиска без дополнительных операций балансировки, применяемых для устранения перекосов структуры дерева.
В индивидуальном задании требуется по заданной последовательности чисел построить бинарное дерево поиска, для числа, введённого с клавиатуры, выполнить удаление из дерева, вывести оставшиеся числа обходом слева направо и после выполнения программы очистить память, занятую древовидной структурой.
В отчёте описан алгоритм решения задачи, включая вставку пары (K, V) с заменой значения при совпадении ключа, поиск и удаление вершины. Приведена оценка трудоёмкости: максимальное количество сравнений при поиске связано с высотой дерева, а трудоёмкость удаления сопоставима со случаем добавления в случайное дерево поиска.
Структура отчёта включает разделы «Тема работы», «Цель работы», «Индивидуальное задание», «Алгоритм решения задачи», «Результаты работы программы» и «Выводы», а также приложение с листингом программы.