c++ - Design and implementation of a 2-3 tree with polymorphism -

i have implement 2-3 tree using base class of node , derived class of leaf , innernode (i.e both "are-a" node).

but don't understand how start insertion in simple cases. since call methods of node insert, how supposed know if insert needs innernode or leaf? , how node supposed change leaf or innernode?

any tips/ideas on how approach this?

here's structure, didn't far though.

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

note: in 2-3 tree, data sits in leaves.

one way of doing things follows. there others.

have 4 separate classes: 2-leaf-node, 3-leaf-node, 2-internal-node , 3-internal-node. solution gets rid of vectors , minimises dynamic allocations.

one inserts element, not node. each node knows inserted element. internal node passes element 1 of child nodes. leaf node absorbs element.

a 2-node absorbs element becoming 3-node. 3-node absorbs element becoming 2 2-nodes, , passing element parent absorb. parent changes , may pass element up. continues until 2-node changes 3-node (its parent doesn't need change, replace child pointer), or element propagates way root, , new root created.

how node "becomes" else? cannot. instead, creates new thing(s) should become, copies information new thing(s), returns newly created thing(s) caller, , deletes itself. caller either replaces old child newly created one, or "becomes" else.

the insert method signature of node this:

 typedef enum {none, expand23, split322} action;  action node::insert(info& element, node*& newnode1, node*& newnode2); 

if node 2-node , became 3-node, method creates new 3-node , passes in newnode1. parent has replace corresponding child pointer upon seeing expand23. parent doesn't expand or split, its insert returns none.

if node 3-node , splits, method creates 2 new 2-nodes , passes them in newnode1 , newnode2. passes element parent absorb. parent either expand23 or split322 depending on type is.

if root returns split322, new root created

"in 2-3 tree, data sits in leaves" — noticed remark. i'm not sure how ever work. 2-3 tree has either 1 or 2 data items in each node, not leaves. cannot work otherwise. pretty ignore remark.

if don't want have separate classes 2- , 3-nodes, don't need expand23 because 2-node can turn 3-node without having delete itself. split322 remains same. not use vectors in case. since leaf nodes store copies of keys exist elsewhere, can stored 3 (smart) pointers keys (not array, 3 separate variables). distinguish between 2-node , 3-node looking @ third pointer. if it's nullptr, 2-node. same thing data in leaves, store in 3 separate pointers.