Stack Exchange
Using Inheritence efficiently in C++
Below is the code I have written in for inserting a node into the Simple Binary Search Tree. Now I am trying to implement the Red Black Tree by inheriting the same Node class into RBNode class.
void Node::insert_node(Tree *t)
{
    Node *cur_node = t->get_root();
    Node *prev_node;
    while(NULL != cur_node)
    {
        prev_node = cur_node;
        if(this->data < cur_node->data)
        {
            cur_node = cur_node->left;
        }
        else
        {
            cur_node = cur_node->right;
        }
    }


    if(NULL == t->get_root())
    {
        cur_node = this;
        t->set_root(cur_node);
    }
    else
    {
        if(this->data < prev_node->data)
        {
            prev_node->left = this;
        }
        else
        {
            prev_node->right = this;
        }
        this->parent = prev_node;
    }
}

This function will remain the same for RBNode, except that Node*  should be replaced by RBNode* and Tree* is replaced by RBTree*. I think it's futile to write the same function in RBNode class which essentially does the exact same thing. If I use the same function, I can't access the RBNode's members, since what I have inserted into the Tree is Node.
What is the effiecient way to achieve this . I am new to C++, so if I have missed anything obvious, please let me know.

If you are aiming for greatest efficiency, a data structure like this involves a lot of loose pointer chasing which can result in lots of cache misses. A more contiguous data structure like a B+ tree will probably be faster. Also, depending on your actual typical data, you might not even need a tree.

You don't need to use inheritance at all but you can. A solution without inheritance would be to use templates. As follows:
template <class N, class T>
void insert_node(N *node, T *tree);

This code will work for both kinds of nodes. The problem with this is that it has to be located either globally or in a third unrelated class. You can have Node inherit from an abstract class INode and Tree inherit from an abstract class ITree. This function will be located in INode. The derived nodes and trees will have any functionality unique to them.

If RBNode inherits from Node and RBTree inherits from Tree, then a RBNode is a Node and a RBTree is a Tree. In fact, as long as this function is public or protected, and the inheritances themselves are public or protected, you will be able to call it on a RBNode and it will work.
Here's a small example:
class Base {
    public:
    int foo() {return 2;}
};

class Derived : public Base {
    //nothing
};

int main() {
    Derived d;
    cout<<d.foo()<<endl; //prints 2
}


Yes. But I can't access the RBNode's members if I use the same function.

No, you won't be able to access any RBNode-specific members. However, you will be able to access any members which are also members of Node. If your goal is to have different behavior in this function, then you either should use a different function (since you want different behavior), or better, use a virtual function in Node which RBNode overrides. You can also look into dynamic_cast, but that is not always the best option.

Thanks a lot for the inputs. I used the templates to fix the issue.
