Одной из задача курсового проекта была следующая: исследовать одну из операций над элементами; построить зависимость времени выполнения операции от числа элементов, над которыми она выполняется. Для ее выполнения потребовалось написать отдельный скрипт, указанный в приложении А.4. Также необходимо было определиться с операцией, которая нужно исследовать. В ходе исследования производительности каждой и операций (добавление, удаление, подсчет количества узлов, поиск) вывод получился такой: оценить время выполнения операции добавления, удаления или поиска узла средствами языка Python не предоставляется возможным, так как асимптотическая сложность в среднем случае будет логарифмической - 
, так как при каждом сравнении будет отбрасываться правая или левая половина поддерева, и для нахождения значения, лежащего на дне дерева, понадобиться log n сравнений; аналогичная ситуация и с добавлением или удалением. В худшем случае асимптотическая сложность будет линейной - 
, однако реализовать худший случай получится только для ~999 узлов. Процесс взаимодействия с поддеревьями рекурсивный (за исключением удаления элемента, его логика построена на цикличном спуске), а Python не позволяет уходить рекурсивно на глубину более 1000. Для худшего случая в 999 узлов средствами языка Python время измерить не предоставляется возможным, процесс происходит настолько быстро, что время, замеренное в наносекундах, показывает нулевые результаты. Асимптотическая сложность подсчета размера дерева – линейная 
, и в худшем, и в среднем случаях, так как для данной операции требуется осуществлять полный обход дерева. И при ее реализации глубина рекурсии не достигает критического значения. Тогда, рассмотрим операцию подсчета количества узлов и построим график зависимости времени выполнения операции от количества узлов в бинарном дереве.
Для выполнения данной задачи использовался скрипт, код которого представлен в приложении А.4. Были проведены замеры времени выполнения операции для деревьев размером от 10000 до 1 000 000 узлов. Шаг размера – 10000. В итоге были проведены 100 замеров для деревьев разных размеров. Результат был сохранен в файл, созданный директории, где находился сам скрипт. Формат записи был следующим: {размер бинарного дерева}:{время выполнения в микросекундах}. Также полученные данные представлены в приложении Б.5. График зависимости времени выполнения операции от размера последовательности можно увидеть на рис. 4.2.1.
Рисунок 4.2.1 - График зависимости времени выполнения операции от размера последовательности
СОПРОВОЖДЕНИЕ
Программный продукт транслировался с помощью средств языка программирования Python версии 3.9.1. Продукт может быть использован на любой операционной системе, которая поддерживает Python 3.9.1. Для запуска продукта необходимо предварительно установить Python на компьютер; затем следует открыть командную строку, написать команду «python [путь до директории с исходными файлами]/main.py». Для выбора необходимого пункта меню стоит ввести номер пункта в консоль и нажать Enter. Далее следовать подсказкам и указаниям в программе. Чтобы прервать работу с продуктом, можно выбрать соответствующий пункт меню, либо закрыть командную строку.
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсового проекта были закреплены знания и навыки работы с языком программирования Python. Были написаны классы, реализующие функционал бинарного дерева поиска. Для проверки работоспособности классов было спроектировано и собрано тестовое приложение, позволяющее взаимодействовать с бинарным деревом в полной мере. Также в ходе тестирования приложения были оценены операции добавления, удаления, поиска узлов, а также операции вычисления высоты и размера бинарного дерева; по каждой операции были сделаны выводы о ее производительности.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Бинарное поисковое дерево // visualgo.net URL: https://visualgo.net/ru/bst
2. Binary Search Tree Visualization // cs.usfca.edu URL: https://www.cs.usfca.edu/~galles/visualization/BST.html
3. BinaryTreeVisualiser // btv.melezinek.cz URL: https://btv.melezinek.cz/binary-search-tree.html
ПРИЛОЖЕНИЯ