I am trying to build 2 functions of a B-tree. However I am finding very little success. It seems the farther I get it to it, the more lost I become, so I am starting over from scratch, and hopefully someone can help me complete this. I have looked at the code from http://cis.stvincent.edu/swd/btree/btree.html but it seems to have just confused me more, I am just trying to make a simple tree for now, so that I can grasp the concept. Hopefully someone will have the patience to help me out on this. Thanks in advance.

The functions are :

Btree insertItem(key k, element e) //Inserts an item and returns the root
find (key k) //Finds a key

When the tree is declared in the main it tells it what the key type, data type, and order will be, example:

int keys; char elements; int order = 5;
btree<keys, elements, order>;

Hopefully this is enough info.

Here is what I have so far (granted little)

template <class Key, class Element, int Order, 

typename BTItem = Item<Key, Element >> 

class Btree {


class BTNode {


            BTItem records [Order  1]; 

            BTNode * nodePtrs [Order];

            BTNode *parent; 

            int nItems; // items in node

            bool isLeaf(void) {return (nodePtrs[0] == NULL);};


class  Position {


        BTNode * nodeptr;

        int  arrayloc;       


Position (BTNode * n = NULL, int al = 0) {nodeptr = n; arrayloc = al;}

Element& element ( ) const (return nodeptr->records[arrayloc].element();)


            BTNode <BTItem> * root; 

            int numItems; // total number of Items in the table

            BT (void) { numItems = 0; nItems = 0;}; // constructor

            ~BT (void) {};


            int size ( ) { return numItems;}; 

            bool isEmpty() {return (numItems == 0;};

            Position find(Key k);

           Btree * insertItem (Key k, Element e){
           if (nItems != order - 1){
              k.records[nItems] = e;
              split() //I am totally lost on how to START splitting a leaf