Как написать конструктор шаблонного класса АВЛ-дерево?

Question

[newmersedez]

Задача заключается в следующем:

0. Опишите абстрактный шаблонный класс binary_tree, представляющий собой абстракцию дерева поиска (тип элементов указывается в единственном параметре шаблона). Класс должен содержать три чистых виртуальных функции: добавления элемента в дерево, удаления элемента из дерева, поиска элемента в дереве по значению. Конструктор класса должен принимать в качестве параметра шаблонный компаратор (правило вычисления отношения порядка между данными в узлах дерева), реализованный в виде объекта стратегии (см. паттерн “Стратегия”).

1. На основе класса из задания 0 реализуйте шаблонный класс АВЛ-дерева. Сгенерируйте псевдослучайные выборки данных и на их основе проведите сравнительный анализ времени работы и количества операций поворотов в алгоритмах вставки / удаления / поиска для АВЛ-дерева

Пока что я написал только задание 0, вот код из файла binary_tree.h(виртуальные функции закоментировал, потому что приступлю к их переопределению позже):

#pragma once
 
/* Comparator */
 
template <typename T>
class   Comparator
{
    public:
        virtual ~Comparator() {}
        virtual int compare(const T &obj1, const T &obj2) const = 0;
};
 
/* Template binary tree class */
 
template <typename T>
class   binary_tree
{
protected:
    struct          btree_node
    {
        T           *data;
        btree_node  *left;
        btree_node  *right;
    };
 
protected:
    Comparator<T>       *compare;
    struct btree_node   *node;
 
public:
    binary_tree(Comparator<T> *compare);
    ~binary_tree();
    
    void            set_comparation_strategy(Comparator<T> *compare);
    // virtual T        *add_node(const T &elem) = 0;
    // virtual T        *find_node(const T &elem) = 0;
    // virtual void delete_node(const T &elem) = 0;
 
private:
    void            delete_tree(btree_node *node);
};
 
template <typename T>
binary_tree<T>::binary_tree(Comparator<T> *compare)
{
    node = nullptr;
    this->compare = compare;
}
 
template <typename T>
binary_tree<T>::~binary_tree()
{
    if (compare != nullptr)
        delete compare;
    if (node != nullptr)
        delete_tree(node);
}
 
template <typename T>
void    binary_tree<T>::set_comparation_strategy(Comparator<T> *compare)
{
    if (this->compare != nullptr)
    {
        delete this->compare;
        this->compare = compare;
    }
}
 
template <typename T>
void    binary_tree<T>::delete_tree(btree_node *node)
{
    if (node)
    {
        delete_tree(node->left);
        delete_tree(node->right);
        delete node;
    }
}

Далее я попытался реализовать класс АВЛ-дерева, и пока что вышло вот это(файл avl_tree.h):

#pragma once
 
#include "binary_tree.h"
 
template <typename T>
class Comporator_avl_tree : public Comparator<T>
{
    virtual int compare(const T &obj1, const T &obj2) const override
    {
        if (obj1 > obj2)
            return (1);
        else if (obj1 < obj2)
            return (-1);
        return (0);
    }
};
 
template <typename T>
class avl_tree : public binary_tree<T>
{
private:
    int *key;
 
public:
    avl_tree();
    ~avl_tree();
};
 
template <typename T>
avl_tree<T>::avl_tree()
{
    
    key = new int;
    if (key != nullptr)
        *key = 0;
}
 
template <typename T>
avl_tree<T>::~avl_tree()
{
    if (key != nullptr)
        delete key;
}

То есть я создал производный класс от класа компоратора, в котором переопределил стратегию(пока что неправильно для авл дерева, это просто тестовый вариант).
В функции main я пытаюсь создать экземпляр класса avl_tree, но выдает следующую ошибку:

In file included from main.cpp:3:
avl_tree.h: In instantiation of ‘avl_tree<T>::avl_tree() [with T = int]’:
main.cpp:9:16: required from here
avl_tree.h:30:23: error: no matching function for call to ‘binary_tree<int>::binary_tree()’
30 | avl_tree<T>::avl_tree()
| ^
In file included from avl_tree.h:3,
from main.cpp:3:
binary_tree.h:44:1: note: candidate: ‘binary_tree<T>::binary_tree(Comparator<T>*) [with T = int]’
44 | binary_tree<T>::binary_tree(Comparator<T> *compare)
| ^~~~~~~~~~~~~~
binary_tree.h:44:1: note: candidate expects 1 argument, 0 provided
binary_tree.h:16:7: note: candidate: ‘constexpr binary_tree<int>::binary_tree(const binary_tree<int>&)’
16 | class binary_tree
| ^~~~~~~~~~~
binary_tree.h:16:7: note: candidate expects 1 argument, 0 provided

Так вот, собственно, в чем заключается мой вопрос. Как правильно написать конструктор для класса avl_tree и как привязать стратегию(объект класса Comparator_avl_tree)?

Answer 1

[vanyamba-electronics]

#include <iostream>

using namespace std;

typedef enum {
    NotEqual,
    Less,
    Equal,
    Greater
} CompareResult;

template <typename _T>
struct CF {
    typedef CompareResult (*CompareFunc)(const _T&, const _T&);
};

template <typename _T>
class avl_tree
{
protected:
    typename CF<_T>::CompareFunc m_cf;
public:
    avl_tree(typename CF<_T>::CompareFunc func) : m_cf(func), m_tree(nullptr) {}
};

CompareResult compare_int(const int& item1, const int& item2)
{
    if (item1 < item2)
        return Less;
    if (item1 > item2)
        return Greater;
    return Equal;
}

int main()
{
    avl_tree<int> int_tree(compare_int);
    return 0;
}

Я также попробовал реализовать это дерево, но в нём нет строгой логики. Всё прекрасно, когда элементов 3. Но когда встаёт задача вставить четвёртый, то возникает вопрос, какую форму должна принять эта структура. А правило говорит, что ветви, исходящие от верхнего элемента должны различаться по высоте не более, чем на единицу.
Ну, допустим, что у нас 4 элемента. Можно изъять из дерева 1 элемент, из трёх выбрать верхний и как-то вставить четвёртый. Теоретически должно работать, но на практике такое решение может привести к тому, что будут варианты бесконечного изъятия лишних элементов, чтобы вставить их куда-то.
Нужно строгое правило, чтобы этого не происходило.