В этом задании вам необходимо реализовать сбалансированное двоичное дерево поиска - иерархичную структуру данных в pointer machine model, узлы которой содержат значения, а также некоторые имеют левого и/или правого потомка, каждый из которых является корнем левого и правого поддеревьев соответственно. Узлы без потомков называются листями, остальные - внутренними. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем (в дереве всегда только один корень).
Все значения в левом поддереве узла меньше, чем значение в самом узле. Аналогично, все значения в правом поддереве - больше, чем значение в узле.
Введем понятие высоты узла:
- Высота листа равна нулю
- Высота внутреннего узла равна максимуму между высотами его потомков, увеличенному на один
Высота дерева определяется как высота его корня.
Дерево называется сбалансированным, если его высота не превышает значение C·log(n) для некоторого C, где n - это количество элементов в дереве.
Ваша модификация - Scapegoat дерево с ручным управлением памятью (без использования умных указателей) на множестве целых чисел (int).
Особенность данной модификации заключается в том, что в Scapegoat дереве вводится коэффициент сбалансированности, который показывает, насколько дерево может быть несбалансированным. Когда этот коэффициент становится слишком большим, выбирается так называемый "козел отпущения", за счет которого происходит перебалансировка.
В задании основной акцент ставится на отсутствие утечек памяти, а также грамотное вынесение общего кода. Подсказки для реализации вашей структуры можете найти на Викиконспектах или на записи лекции по АиСД.