c++ - 将BST继承为黑红树的问题

Question

由于黑红树是二叉搜索树我决定使用继承来实现。简而言之，节点继承在我的代码中是这样的:

struct BST_node
{
   // public interface here

   int key;
   BST_node* left;
   BST_node* right;
   BST_node* parent;
};

struct BRT_node : BST_node
{
   // public interface here

   NodeColour colour;
};

我遇到的问题是派生类中的指针是基类的类型。因此，如果没有显式转换，我不能在派生类的上下文中使用它们。也许隐藏成员和使用虚拟访问器方法可以达到目的，但这会破坏这个简单的语法:

node->left = node->parent;

有更好的方法吗？

Answer 1

将所有数据成员放在 BRT_node 中有什么问题？

struct BRT_node
{
    int key;
    BRT_node* next;
    BRT_node* prev;
    BRT_node* parent;
    NodeColour colour;
};

这样，您就可以保留 node->left = node->parent; 的“漂亮语法”。

这里使用继承的问题是因为红黑树算法需要BRT_node，而不是BST_node。所以在这种情况下继承是不合适的。