Написать программу для работы по запросам оператора с упорядоченной табли-цей, реализованной в виде двоичного идеально сбалансированного дерева поиска (для любого узла количество узлов в правом и левом поддеревьях отличается не более, чем на 1).

Ключ – целое число. Информация – строка произвольной длины.

Узел дерева содержит ключ, указатели на правое и левое поддеревья и указатель на информационное поле. В узел дерева могут быть включены дополнительные поля для подержания балансировки (для хранения коэффициента перевеса).

В таблице не могут храниться записи с одинаковыми ключами.

Предусмотреть следующие операции:

- включение нового элемента в таблицу без нарушения свойств упорядоченно-сти; если информация с заданным ключом уже есть, то выводится сообщение об ошибке;

- удаление из таблицы элемента, заданного своим ключом, без нарушения свойств упорядоченности таблицы;

- поиск информации по заданному ключу;

- вывод всего содержимого таблицы в прямом порядке следования ключей;

- возврат элемента, соответствующего минимальному значению ключа.

Примечания:

1. Программа должна содержать несколько функций; функция main() должна выполнять: вывод меню, ввод и анализ ответа, вызов на исполнение требуемой функции.

2. В программе нужно предусмотреть проверку правильности ввода данных.

3. Оценить сложность реализованных алгоритмов.

4. (*) Для целей отладки реализовать форматированный вывод таблицы в виде дерева.

5. (*) Для целей отладки реализовать загрузку таблицы из файла в формате

· Ключ1

· Инофрмация1

· Ключ2

· …

6. (*) Провести таймирование (или профилирование) программы.