Студент

Дмитриенко Михаил

Задача

Декартово дерево

Состояние

Завершено

Баллов

4

Дедлайн

Назначено

23.10.2018, 10:39

Завершено

25.12.2018, 09:07

Задание

Произвести рефакторинг модуля, реализующего декартово дерево (treap = tree + heap = дерамида).

Исходный код

• treap.h – интерфейс дерамиды,
• treap.c – реализация дерамиды,
• fatal.h – обработка ошибок,
• testtrp.c – простой тест.

Описание

В процессе рефакторинга необходимо:

• Переписать код на C++ (new, delete, объявление переменных не в начале блока, а там где они реально используются, и т. п.)
• Текстовый ввод и вывод производить через std::cout и т.п
• Избавиться от define'ов (объявление констант) и глобальных переменных.
• Уйти от работы с указателями в пользу ссылок, где это возможно.
• Вместо typedef int ElementType использовать шаблоны.
• Предусмотреть возможность передачи в качестве параметра шаблона нетривиальных типов данных (потребуется передача функционального объекта, аналогичного std::less).
• Избавиться от typedef struct TreapNode *Position создав итератор.
• Обработку ошибок перенести на механизм исключений и std::exception.
• Выделить класс дерамиды, глобальные функции для работы с дерамидой преобразовать в методы.
• Выделить класс узла дерева – оформить как внутренний класс дерамиды.

В целом, получившийся класс должен приближаться к интерфейсу std::set по мере возможностей (принципиально новый функционал дописывать не нужно).

Архив с проектами для Visual Studio 2013 и Visual Studio 2015.

Примечания

Не доделал итераторы по бинарному дереву.