Balancing a Binary Tree: Testing the Implementation

Now that all the easy work is done we get to the hard part: writing a test driver to verify that it was done right. Whatever we do, our test driver is going to get complicated. So I propose that we keep it simple wherever we can; in particular, I suggest, for the purposes of this discussion, that we write several discreet drivers instead of rolling all our tests into a single program, and that we don't try too hard to fully automate the process; instead we can display results at various points, and eyeball the display to make sure that the results are valid. We'll leave it as an exercise to the reader to bolt our test drivers together and massage them into a single process that can be fully automated.

Our first question, of course, is just what do we need to test? Our biggest changes to the BTREE module were adding the delete, recycle and validate methods, the statistics facility and, of course, the balance method. We also had to modify the various the add utilities to utilize the new recycling logic. Testing in each of these areas is described below. In addition, we probably shouldn't miss the opportunity to see how fast (or slow) our implementation is, so we'll build some timing analysis into the test drivers, as well.

Table of Contents

1. Testing BTREE_validate
2. Testing the Statistics Facility
3. Testing BTREE_delete_node
4. Testing the Recycling Logic
5. Testing BTREE_balance

Next: Testing BTREE_validate