How to write an AVL tree template class constructor?

Question

OOP

The task is as follows:

0. Describe the abstract template class binary_tree, which is an abstraction of the search tree (element type is specified in the only template parameter). The class must contain three pure virtual functions: adding an element to the tree, removing an element from the tree, searching for an element in the tree by value. The class constructor must take as a parameter a template comparator (the rule for calculating the order relation between data in tree nodes) implemented as a strategy object (see the “Strategy” pattern).

1. Based on the class from task 0, implement the AVL tree template class. Generate pseudo-random data samples and, based on them, perform a comparative analysis of the running time and the number of rotation operations in the insert / delete / search algorithms for the AVL tree

So far, I have only written task 0, here is the code from the binary_tree.h file (I commented out the virtual functions, because I will start redefining them later):

#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;
    }
}

Next, I tried to implement the AVL tree class, and so far this has come out (file 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;
}

That is, I created a derived class from the comporator class, in which I redefined the strategy (so far, this is not correct for the avl tree, this is just a test case).
In the main function, I'm trying to instantiate the avl_tree class, but I'm getting the following error:

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

So here is what my question is. How to correctly write a constructor for the avl_tree class and how to bind a strategy (an object of the Comparator_avl_tree class)?

Answer 1

#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;
}

I also tried to implement this tree, but there is no strict logic in it. Everything is fine when there are 3 elements. But when the task arises to insert the fourth one, the question arises what form this structure should take. And the rule says that the branches emanating from the top element should differ in height by no more than one.
Well, let's say we have 4 elements. You can remove 1 element from the tree, select the top one from the three and somehow insert the fourth one. Theoretically, it should work, but in practice, such a solution can lead to the fact that there will be options for endless removal of unnecessary elements in order to insert them somewhere.
You need a strict rule to prevent this from happening.