c++ - B+树节点实现

Question

我正在为一个类实现 B+Tree。节点目前是这样实现的:

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;
        }
};

当我想向叶节点添加一个元素时(通过访问 LeafNode->data)，我得到

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

我猜这是因为编译器不知道我正在访问的节点是内部节点还是叶节点，尽管我首先使用 isLeafNode() 对其进行了检查。 我无法将这两个类合并为一个类，因为叶节点比内部节点需要多一个 Bucket 来存储数据。

我意识到这是一个设计问题，但是否有一些我缺少的解决这个问题的简单方法？我是 C++ 的新手。

Answer 1

你真的应该为这样的事情使用虚拟方法。您可以更改 isLeafNode() 查询以返回指向叶节点的指针(如果它是一个)，否则返回 NULL。

class LeafNode; // forward declare

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

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

然后，如果 Node 实际上是 LeafNode，您可以使用此方法访问 data。