CODEWITHSUNDEEP
c++inheritance
Rohit Walavalkar
Rohit Walavalkar

Reputation: 818

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.

Upvotes: 0

Views: 88

Answers (2)

Benjy Kessler
Benjy Kessler

Reputation: 7616

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.

Upvotes: 2

IanPudney
IanPudney

Reputation: 6021

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
}

Upvotes: 2

Related Questions