Programming Assignment II: B-Trees

Part I Due Mon., November 10th

Part II Due Fri., November 21st

Introduction

The goal of this assignment is to implement B-trees, as described in section 4.7 of the textbook. Because B-trees are rather complicated, you will be given a large amount of initial code, and you will also be asked to turn in pseudocode for your B-tree functions in advance. In view of this assignment and the midterm on Nov. 14, there will be no problem sets due during the weeks of Nov. 10 and Nov. 17. However, you will be provided with practice problems to help in your preparation for the midterm. Take it from someone who just spent two long days writing 1,300 lines of B-tree code: this is not a trivial assignment. Even with the starting code, you will have to write approximately 300 lines. Start early!

Specific Instructions

Part I (due Nov. 10th)

Get the skeleton code from the Programming Assignments web page and study what you are given. Of particular interest is the BTreeNode class, which contains a lot of useful methods for manipulating nodes. This allows you to write methods more abstractly in the BTree class. The BTree class contains the methods which you are responsible for writing, Find(), Insert(), and Remove(). Both the BTreeNode and BTree classes are templates with two parameters, the first being the type of the key and the second being the type of the data associated with the key.

For Part I, write pseudocode for the BTree methods, using the BTreeNode operations to help you. You must hand in your pseudocode in class on the Part I due date above.

Part II (due Nov. 19th)

Implement the Find(), Insert(), and Remove() methods for the BTree class. You may not change the prototypes for any of these methods, since they are used as they are currently defined in the testing module. However, you may (and probably should) add extra private helper methods. To give you some hints on these, I have left comments showing the helper methods I used in my implementation. You should not need to modify any files except Btree.h and BTree.cpp.

To test your program, I have included a sample program which lets you insert, find, and remove numeric keys with associated strings as data. For example, you could insert the pair (9430524, "Daniel Fasulo"). The program also lets your print your tree to inspect it for errors. You should be able to put all of the supplied files into a directory, type make, and end up with a program called btree. To run the program, simply type btree; it will then give you a self-explanatory menu of options.

By the Part II due date, you should turn in all of the files associated with your project, meaning the implementation (.cpp) files, the header (.h) files, and the makefile. This includes the initial code I gave you. As usual, you are responsible for turning in a hardcopy in class and performing an electronic turnin using the turnin program.

As I mentioned in section, the handling of templates is very compiler-specific. Even if you choose to write your code on some other platform, your final submission must compile and run on the instructional Alphas, sanjuan and orcas.

Tips

Don't forget to take advantage of input and output redirection, as described in the tips for the first assignment. In particular, saving a file with a series of commands for the test program can save you lots of tedious typing, and saving the output to a file can let you browse the trees you print more conveniently.
The code I gave you is based on a fully-function program, and so it should hopefully be correct. However, in the unlikely event that a bug is found, mail me and I will update the file. The Programming Assignments page is set up to clearly show the last time a distribution file was modified, so it should be convenient to figure out if you need an update.
Construct your program by writing and debugging the Insert() and Find() methods first, and the doing the Delete() method. It is better (from a grading as well as practical perspective) to have a functioning program that implements a subset of the specification than one that does not compile or run at all.
The BTreeNode class aggressively uses assertions to check the preconditions for its functions. If an assertion fails (at least on a UNIX computer), the program will halt and perform a core dump, just as if it had crashed. To use gdb to examine the core file (called core), you can type
```
           gdb btree core
      
```
This will let you view the program's state when it crashed.
In case I didn't mention it before, start early!

Maintained by:
dfasulo@cs.washington.edu
(Last Update: )