Разработка АТД "Бинарное дерево поиска"

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

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

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

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

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

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

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

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

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

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

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

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

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

• обход дерева по схеме, Lt->t->Rt

• Алгоритмы программы в рекурсивной форме

• Доп. функция: удаление узла дерева на основе метода объединения двух поддеревьев удаляемого узла (рекурсивная форма)

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

операции:

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

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

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

меню операций.

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

элементов для среднего и худшего случаев.

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

операций.

5. Составить отчѐт по контрольной работе .