B+ Tree node implementation

Question

Im implementing a B+Tree for a class. The Nodes are currently implemented like this:

class Node {
    public:
        E* keys[order*2];
        Node *children[order*2+1];
        int size;
        Node(){ 
            size = 0;
        }
        bool empty() {
            return size == 0;
        }
        bool isLeafNode() {
            return false;
        }
};

class LeafNode : public Node {
    public:
        E* data[order*2+1];
        bool isLeafNode() {
            return true;
        }
};

When I want to add an element to a leaf node (by accessing LeafNode->data), I get

 error: request for member ‘data’ in ‘left<int>’, which is of non-class type ‘BTree<int>::LeafNode*()’

I guess this happens because the compiler doesn't know whether the Node I'm accessing is an inner- or leaf-node, although I'm checking it first by using isLeafNode(). I can't merge the two classes into one, because the Leaf Nodes need one more Bucket for the data than the inner nodes.

I realize this is sort of a design-question, but is there some trivial approach to this problem that I'm missing? I'm fairly new to C++.

Answer 1

You really should use a virtual method for something like this. You can change your isLeafNode() query to return a pointer to the leaf node if it is one, and NULL otherwise.

class LeafNode; // forward declare

class Node {
//...
public:
    virtual ~Node () {}
    virtual LeafNode * isLeafNode () { return 0; }
    //...
};

class LeafNode : public Node {
//...
public:
    LeafNode * isLeafNode () { return this; }
    //...
};

Then, you can use this method from a Node to access the data if it is actually a LeafNode.

Answer 2

The error message

error: request for member ‘data’ in ‘left<int>’, which is of non-class type  ‘BTree<int>::LeafNode*()’

and other errors of this form usually mean that you are trying to access a field of a struct using a . when you should be using ->. For example, if you have

LeafNode* ptr = /* ... */;
ptr.data[0] = /* ... */;

You will get an error on the second line, because you are using . instead of ->.

Try seeing if this is the error you're having on the indicating line and, if so, change the dot to an arrow.

Hope this helps!