c++ - 如何从普通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 .

我试图在中的方法中，在构造函数上(但不能转换nullptr)将node的变量覆盖到rb_node rb_node 到返回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;
    ...
};