B-Tree

Hello,

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)

Code:

---


template <class Key, class Element, int Order,

typename BTItem = Item<Key, Element >>

class Btree {

protected:

class BTNode {

public:

            BTItem records [Order – 1];

            BTNode * nodePtrs [Order];

            BTNode *parent;

            int nItems; // items in node

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

};

class  Position {

private:

        BTNode * nodeptr;

        int  arrayloc;     

public:

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

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


private:

            BTNode <BTItem> * root;

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

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

            ~BT (void) {};

public:

            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;
              nItems++;
              numItems++;
          else
              split() //I am totally lost on how to START splitting a leaf


}

---