В этом задании вам необходимо реализовать сбалансированное двоичное дерево поиска - иерархичную структуру данных в pointer machine model, узлы которой содержат значения, а также некоторые имеют левого и/или правого потомка, каждый из которых является корнем левого и правого поддеревьев соответственно. Узлы без потомков называются листями, остальные - внутренними. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем (в дереве всегда только один корень).
Все значения в левом поддереве узла меньше, чем значение в самом узле. Аналогично, все значения в правом поддереве - больше, чем значение в узле.
Введем понятие высоты узла:
- Высота листа равна нулю
- Высота внутреннего узла равна максимуму между высотами его потомков, увеличенному на один
Высота дерева определяется как высота его корня.
Дерево называется сбалансированным, если его высота не превышает значение C·log(n) для некоторого C, где n - это количество элементов в дереве.
Ваша модификация - сплей-дерево с ручным управлением памятью (без использования умных указателей) на множестве целых чисел (int).
Особенность данной модификации заключается в том, что в сплей-дереве есть специальная операция splay, которая позволяет поддерживать баланс в дереве.
Ваша реализация должна удовлетворять интерфейсу, изложенному в файле include/SplayTree.h:
class SplayTree
{
public:
bool contains(int value) const;
bool insert(int value);
bool remove(int value);
std::size_t size() const;
bool empty() const;
std::vector<int> values() const;
~SplayTree();
};В задании основной акцент ставится на отсутствие утечек памяти, а также грамотное вынесение общего кода. Подсказки для реализации вашей структуры можете найти на Викиконспектах или на записи лекции по АиСД.