АТД "BST - дерево"

Файл с заданием вложен. Вариант №2

Спроектировать, реализовать и провести тестовые испытания АТД "BST - дерево" для коллекции, содержащей данные произвольного типа. Тип коллекции задаѐтся клиентской программой. Программа может быть реализована на одном из следующих языках программирования Java, C++. Операционная система любая

Интерфейс АТД "BST - дерево" включает следующие операции:

опрос размера дерева, 

очистка дерева, 

проверка дерева на пустоту,

 поиск элемента с заданным ключом,

 включение нового элемента с заданным ключом

,  удаление элемента с заданным ключом,

 итератор для доступа к элементам дерева с операциями:

1) установка на корень дерева,

2) проверка конца дерева,

3) доступ к данным текущего элемента дерева,

4) переход к следующему по значению ключа элементу дерева,

5) переход к предыдущему по значению ключа элементу дерева, 

обход дерева по схеме, заданной в варианте задания,  дополнительная операция, заданная в варианте задания (см. алгоритм операции в приложении

3). Для тестирования коллекции интерфейс АТД "BST - дерево" включает дополнительные операции:

 вывод структуры дерева на экран,

 опрос числа просмотренных операцией узлов дерева.

2. Выполнить отладку и тестирование всех операций АТД "BST - дерево" с помощью меню операций.

3. Выполнить тестирование средней трудоѐмкости операций поиска, вставки и удаления элементов для среднего и худшего случаев.

4. Провести сравнительный анализ экспериментальных показателей трудоѐмкости операций.