Rewriting the B-tree

Since nobody was able to successfully complete the B-tree assignment, I am giving everyone a second chance to get it right. In every case, the work submitted did represent significant progress toward completion. In every case, I have added extensive comments to your work to point out what you need to do to correct your mistakes and things that you still need to do to reach a successful conclusion. Although your approach may differ in some ways from the approach I used for my own solution, everyone's strategy for solving the problem was workable and noone should have to rework their program from the ground up.

General suggestions

Since many people made the same mistakes, here are some general suggestions for everyone.

• Whenever you transfer keys from one node to another, you may also need to transfer pointers that hang down from that key.
• When you remove a key from a node, you will have to close any gap that is created by removing that key. After you reduce keyTally by 1, you don't have to worry about keys at position keyTally or pointers at position keyTally+1. Those just get ignored by the logic.
• Be careful with using pointers[0] == 0 as a test for whether or not something is a leaf. Depending on how you do consolidations, sometimes nodes that were internal nodes could switch to being leaves - if those former internal nodes still have residual pointers in them you could get fooled by this test. A better approach is to maintain a leaf flag in each node and carefully check your logic to ensure that that flag is correct at all times.
• You can give your nodes parent pointers, or you can get by without them. If you don't have parent pointers, give some thought to writing a method for your BTree class like parentOf(BTreeNode<T>* node) that can search down the tree and quickly tell you what the parent of node is. (Hint: all nodes contain keys, so the keys in node can guide your search for the parent.) If you do decide to use parent pointers, check your logic carefully to determine that those pointers are correct at all times.
• My solution puts most of the functionality into the node class and uses recursion heavily. Putting most of the functionality into the BTree class and using loops is an equally valid approach.
• Check your logic carefully to see that everything will work regardless what type gets used for the template type T. In typical cases T will be int, double, or string. Will all of your code work correctly for all of those types? What all of these types have in common is that they all define the operations ==, !=, <, and >.
• Check your logic to see if it will work correctly for cases larger than M = 4.
• Comment your code!

Testing your BTree class

I strongly recommend that you implement a visualization scheme for your BTree class. Being able to see what the tree looks like as you insert and delete items is a valuable aid for catching subtle logic errors. Here is the source code for methods I use to emit Mathematica code from my program that can be used to visualize the tree.

My BTree class contains this method:

template <class T,int M>
void BTree<T,M>::snapShot(ostream& out) {
  out << "TreeForm[";
  if(root != 0)
    root->snapShot(out);
  out << "]";
}

and my BTreeNode class contains this method:

template <class T,int M>
void BTreeNode<T,M>::snapShot(ostream& out) {
  out << '\"';
  int n;
  for(n = 0;n < keyTally - 1;n++)
    out << keys[n] << ':';
  out << keys[n] << '\"';
  if(!leaf) {
    out << '[';
    for(n = 0;n < keyTally;n++) {
      pointers[n]->snapShot(out);
      out << ',';
    }
    pointers[n]->snapShot(out);
    out << ']';
  }
}

Please use these methods to help in debugging.

Use methods more aggressively

Another general suggestion I have for everyone is to use additional methods to help break major tasks down into small, more manageable pieces. The general rule I try to follow is that any method that takes up more than one screen should be broken into smaller methods.

Here is a listing of the methods I put in my BTreeNode class to help me do some of the common tasks needed to solve this problem. You should give some thought to breaking your longer methods down into similar short methods to ease the task of writing complex logic.

// Helper function for the splitting process. Shoves a key and 
// child up into a parent node
void insertKey(const T& el,BTreeNode* child);
// Handles the special case of splitting the root
void rootSplit();
// Split an overfull node that is not the root
void split();
// Remove a key from a leaf node
void removeKeyFromLeaf(const T& el);
// Return the rightmost descendent node of this node
BTreeNode* rightmost();
const T& lastKey();
// Which slot is this node a child of?
int parentSlot(BTreeNode* child);
// One of the two children at this slot is undersized - fix things up
void rebalanceAround(int slot);
// Consolidate the root by pulling its two children up into the root
void consolidateRoot();
// Do a normal consolidation at some slot by moving everything from 
// the right child of this slot into the left.
void consolidate(int slot);
// Rotate right around a slot
void rotateRight(int slot);
// Rotate left around a slot
void rotateLeft(int slot);

Testing your BTree class

Below is the code I used in my main program to test my BTree. The test code inserts a number of integers chosen at random, emits a snapshot after every insertion, and then proceeds to delete some randomly chosen integers with a snapshot after each deletion. Feel free to use this test code to test your BTree class both with M = 4 and with larger values of M.

#include <fstream>
#include <stdlib.h>
#include "BTree.h"

using namespace std;

void main() {
  BTree<int,4> x;

  ofstream out("tree.txt");
  for(int n = 0;n < 100;n++) {
    int k = rand()%100;
    if(!x.contains(k)) {
      x.insert(k);
      x.snapShot(out);
      out << endl;
    }
  }

  out << endl;

  for(int n = 0;n < 80;n++) {
    int k = rand()%100;
    if(x.contains(k)) {
      x.remove(k);
      x.snapShot(out);
      out << endl;
    }
  }

  out.close();
}