具有多态性的2-3树的设计与实现

Question

我必须使用 node 的基础 class 和 leaf 的派生 class 和 innernode 来实现 2-3 树（即两个 "are-a" 节点）。

但是我不明白在简单的情况下如何从插入入手。既然我们调用了node的方法来插入，那它怎么知道我们插入的是innernode还是leaf呢？节点如何将自己更改为 leaf 或 innernode？

任何tips/ideas如何解决这个问题？

这是结构，不过我没走多远。

typedef int TreeKey;

class node {
public:
    virtual ~node() {}

    virtual void insert(TreeKey k, string d);
    virtual void deletenode(TreeKey k);
    virtual void findnode();
    virtual node * findnode(TreeKey key);

protected:
    struct info {
        TreeKey key;
        string data;
    };
    node* parent=nullptr;
};

class leaf : node {
    info i;
public:
    virtual void insert(TreeKey k, string d);


};

class innerNode : node {
    vector<info> inf;
    vector<node*> vect;

public:
    virtual void insert(TreeKey k, string d);


};

注意：在这棵 2-3 树中，数据仅位于叶子中。

Answer 1

一种处理方法如下。还有其他的。

有 4 个独立的类：一个 2-leaf-node、一个 3-leaf-node、一个 2-internal-node 和一个 3-internal-node。该解决方案摆脱了向量，因此最大限度地减少了动态分配。

一个插入一个元素，而不是一个节点。每个节点都知道如何处理插入的元素。内部节点将元素传递给 child 个节点之一。一个叶节点吸收元素。

2 节点通过成为 3 节点吸收元素。一个3节点通过变成两个2节点来吸收一个元素，并将一个元素传回它的parent来吸收。然后 parent 本身发生变化并可能向上传递一个元素。这一直持续到某些 2 节点更改为 3 节点（它的 parent 不需要更改，只需替换其 child 指针），或者一个元素一直传播回根，并创建一个新的根。

如何结点"becomes"别的东西？这不可以。相反，它创建它应该成为的新事物，将其信息复制到新事物，returns 新创建的事物给调用者，然后删除自己。然后，调用者要么用新创建的 child 替换旧的 child，要么自己 "becomes" 其他东西。

节点的 insert 方法签名可能如下所示：

 typedef enum {none, expand23, split322} action;
 action Node::insert(info& element, Node*& newNode1, Node*& newNode2);

如果该节点是一个 2 节点并且它变成了一个 3 节点，该方法将创建一个新的 3 节点并将其传递回 newNode1。 parent 必须在看到 expand23 时替换相应的 child 指针。 parent 本身不会扩展或分裂，所以它 insert returns none.

如果该节点是一个 3 节点并且它分裂了，该方法将创建两个新的 2 节点并将它们传递回 newNode1 和 newNode2。它还会传回一个 parent 吸收的元素。 parent 将执行 expand23 或 split322 取决于它是什么类型。

如果根returnssplit322，则创建一个新的根

"in this 2-3 tree, the data sits only in the leaves" — 刚注意到这句话。我不确定这是怎么回事。 2-3 树的每个节点中有 1 或 2 个数据项，而不仅仅是叶子。否则它无法工作。所以我几乎忽略了这个评论。

如果您不想为 2 节点和 3 节点设置单独的类，则不需要 expand23，因为 2 节点可以变成 3 节点而不必删除自己。 split322保持不变。在这种情况下我不会使用向量。由于叶节点只存储存在于别处的键的副本，因此它们可以存储为 3 个（智能）键指针（不是数组，只是 3 个单独的变量）。您可以通过查看第三个指针来区分 2 节点和 3 节点。如果它是 nullptr，则这是一个 2 节点。叶子中的数据也是如此，将其存储在 3 个单独的指针中。

具有多态性的2-3树的设计与实现

Design and implementation of a 2-3 tree with polymorphism

c++

algorithm

polymorphism

tree

c++11