0

Im implementing BinarySearchNode class which inherits from BinaryNode class.

BinaryNode fields are:

//|-------------------- Protected fields --------------------|
protected:
    U value;
    T key;
    BinaryNode<T,U>* left;
    BinaryNode<T,U>* right;
    BinaryNode<T,U>* parent;

and BinarySearchNode does not have any additional fields. I'm getting error with the implementation of the method insert in the BinarySearchNode class:

ifndef BINARYSEARCHNODE_H
#define BINARYSEARCHNODE_H
#include <iostream>
#include "BinaryNode.h"

template <class T,class U>
class BinarySearchNode : public BinaryNode<T,U>
{
public:
//|--------------------- Constructors ----------------------|
    BinarySearchNode(const T key, const U& data): BinaryNode<T,U>(key,data) {}

//|------------------------ Methods ------------------------|

    virtual void insert(const T key, const U& data){            //throw (char*)
        if(key < this->key){
            if(!(this->left)){
               this->left = new BinarySearchNode(key, data);
               this->left->parent = this;
            }
            else
                this->left->insert(key,data);
        }

        if(this->key < key){
            if(!(this->right)){
                this->right = new BinarySearchNode(key,data);
                this->right->parent = this;
            }
            else
                this->right->insert(key,data);
        }
        if(this->key == key)
            throw "Error: Key already exists in the tree.";
    }

The error I get is:

error: 'BinaryNode<int, int>* BinaryNode<int, int>::parent' is protected within this context|

But since BinarySearchNode inherits from BinaryNode I cannot understand why cant I get an access to protected field of the base class.

Any help would be appreciated. Thanks in advance.

DirichletIsaPartyPooper
  • 273
  • 1
  • 7
  • 2
    Tactical note: Are you sure you want to use inheritance in this fashion? It allows trees that can store any tree that inherits from `BinaryNode`. It wouldn't make any sense to have `BinarySearchNode`s mixed in with `NonBinarySearchNode`s. How would inserting work if the rules changed from node to node? How would you search the tree? – user4581301 Feb 03 '22 at 20:56
  • @Passerby Yes, thanks. – DirichletIsaPartyPooper Feb 03 '22 at 20:59
  • @user4581301 What do you mean? all I need is a total order over the type T of the keys – DirichletIsaPartyPooper Feb 03 '22 at 21:00
  • But how can you get that if at one node the total order follows one set of ordering rules in one node and potentially a totally different set of ordering rules in the next node? You're inheriting at the wrong class. Trees can allow inheriting, but the nodes inside a particular tree should always all be the same type. – user4581301 Feb 03 '22 at 21:04
  • When you search this tree, you'll be working with the pointer to base class, not the derived type. Before you can search, you'll have to downcast the object, and the only way for that to be safe is to use something like CRTP. Otherwise, you could mix node types and downcast to the wrong type. – Chris Uzdavinis Feb 03 '22 at 21:04
  • @user4581301 How can the set of ordering rules be different? BinarySearchNode inhertis from BinaryNode, as long as its the same "T", why would the rules change? for example, if T is int, then the order is the same in both classes – DirichletIsaPartyPooper Feb 03 '22 at 21:06
  • @ChrisUzdavinis Why would I want to downcast the object? what's the difference? the search would be the same because all I care about when searching is the key, and the key of the base class and derived class is the same. If you mean that the method of base class woud be activated instead of the derived calss - I defined the search method to be virtual in the base class – DirichletIsaPartyPooper Feb 03 '22 at 21:09
  • I think I'm delving too deep here and getting out of your level of concern. `this->left = new BinarySearchNode(key, data);` in `insert` forces `insert` to only insert `BinarySearchNode`s, so you will likely not encounter the nightmare case I'm outlining and just have a less efficient than optimal solution. – user4581301 Feb 03 '22 at 21:12
  • Regardless of should or should not ``BinarySearchNode`` inherit from ``BinaryNode``, the error message is quite simple: ``this->left`` is OK (``left`` is protected member of ``BinarySearchNode`` but ``this->left->parent`` is not OK ``parent`` is a protected member of the object ``this->left`` – Soulimane Mammar Feb 03 '22 at 21:26
  • And if we srip out athe inheritance and handle it at the Tree, the whole problem just... goes away. – user4581301 Feb 03 '22 at 21:31
  • @user4581301 You were right actually, I had to downcast everytime I used BinarySearchNode methods. I think it would be easier to just define a pure virtual method in the BinaryNode class, anyway I'll probably never create an instance of it (Im using it as a base class for several kind of trees, such as Heaps, BinarySearchTree, AVLTree etc...) – DirichletIsaPartyPooper Feb 03 '22 at 22:28
  • Sounds like you might be conflating nodes with trees. If you make a `Tree` class that can be be specialized by different types of trees, each can contain its own type of `Node`. All of the inheritance overhead moves to where it impacts you once (accessing the tree) and not every time you have to work on a node. Then you'll probably find that inheritance doesn't make much sense either because you'll find A) there isn't really enough cross-over between different types of trees to reduce code duplication and B) few cases where you don't know what sort of tree you want until runtime. – user4581301 Feb 03 '22 at 22:40

0 Answers0