Search code examples
c++oopinheritancetreehierarchy

How to structure the inheritance from generic tree to a-b tree


I am trying to implement an a-b tree, as a derived class from a generic tree. The generic tree node is as follows:

template<typename T>
struct TreeNode
{
    T value;
    std::vector<TreeNode*> children;
    //Some other trivial stuff
};

The structure of the a-b node is as follows:

template<typename T>
struct ABTreeNode : TreeNode<T>
{
    std::vector<T> keys;
    //The idea is to omit the T value field of the base node and use that vector for the keys
};

Also in the generic tree class there exists a root field

TreeNode *root;

And the a-b constructor is

template<Typename T>
ABTree<T>::ABTree(T value)
{
    GenericTree<T>::root = new ABTreeNode;
    root->keys.push_back(value);
}

Now, the way this is made, I need to use down casting in a lot of the a-b tree methods, for example:

template<typename T>
bool ABTree<T>::search(T value)
{
    ABTreeNode *node = GenericTree<T>::root;
    //....
}//Downcast base to derived

As far as I know down casting is a bad practice and indicates bad design. The fact that I use variables defined in the derived struct but declare the node as base struct seems very error prone. What would happen if that node was created as a base node and not derived? Eg:

//Somewhere:
TreeNode *node = new TreeNode;//Instead of new ABTreeNode
//..
//Somewhere else
node->keys//Shouldn't that be an error?

Is my approach correct? If not how should I structure it better?

PS: spare the raw pointers please.


Solution

  • Sharing code by inheritance is a bad design. Better is to use Composition - see https://en.wikipedia.org/wiki/Composition_over_inheritance

    To share code between different implementations of various trees I would extract common fields into a struct.

    template <class T, class ChildT>
    struct TreeNodeCommons
    {
      T nodeValue;
      std::vector<ChildT*> children;
      // more common fields
    }
    

    Then I would attach it to Nodes of different types.

    template<typename T>
    struct ABTreeNode
    {
      TreeNodeCommons<T, ABTreeNode<T>> commons;
      std::vector<T> keys;  
    };
    

    You may then write templated algorithms assuming Node contains field named commons and you may write Node specific algorithms as well. And there is no dynamic_casts.