Как унаследовать красное черное дерево от нормального BST

Question

У меня гигантские проблемы с наследованием.У меня есть нормальный узел следующим образом (пожалуйста, игнорируйте любые опечатки в коде, у меня его сейчас нет, но он прекрасно компилируется)

template<typename T>
class Node {
    Node<T> *parent, *left, *right;
    ...//simple methods
}

затем я реализую нормальный BST, используятолько что созданный узел:

template<typename T>
class tree {
    virtual Node<T>* insert(T value);
    ...// other methods of tree
}

Теперь я хочу создать красное черное дерево, но код для него почти такой же, поэтому я просто пытаюсь переопределить, скажем, вставить:

template<typename T>
class rb_node : public node<T> {
    int color;
    ...//methods to retrieve and set the color as well the constructor
}
template<typename T>
class rb_tree : public tree<T> {
    Node<T> *insert(T value){
        auto z = (rb_node<T>*)tree<T>::insert(value);
        while(z->parent()->color() == RED)...
}

с тех пор, как я произнес, z->parent() распознается как rb_node, но родительский не распознается, так как он был создан в базовом классе, поэтому у него нет метода color().Как мне решить эту проблему, которая убивает меня почти на две недели ??

Obs: если кому-то нужно, мой код на https://github.com/dodonut/Algorithms/tree/master/Data_Structures.

Я пытался переопределить переменныеот node до rb_node в конструкторе (но не может приводить nullptr), в методе из rb_node в return rb_node (но сигнатура методов базового класса отличается)

Answer 1

Одним из возможных решений может быть использование базового класса tree и необязательного аргумента шаблона NodeType?Как и в

template<typename T, typename NodeT = Node<T>>
class tree
{
    ...
    virtual NodeT* insert(T const& value);
    ...
};

Тогда подкласс может использовать свой специальный rb_node:

template<typename T>
class rb_tree : public tree<T, rb_node<T>>
{
    ...
    rb_node<T>* insert(T const& value) override;
    ...
};