Computer Science 230 Assignment 4

Objectives:


to examine and modify a binary search tree ADT

to implement a simplified version of a structure we have learned
about





Requirements:

Discussed the B+
tree, which has all data in the leaves and only keys in the tree. We will
simulate a simplified version of this combination using an array and a binary
search tree. We will call our version the BMinusTree.



Specifications:

Use the AutoPart class from the previous assignment.



Write a DataBank class that contains an array of
AutoPart objects. The constructor
has a single parameter that says how many objects the array can hold. The
method insert() has an AutoPart object as its only parameter. The method inserts the object into
the next available place in the array, and returns an int that says where the object was inserted, or -1 if the insert did not work. The method fetch() has an int parameter
and returns the AutoPart object
at the position indicated, or null if there
is a problem. The method update() has an
int parameter and accesses the AutoPart object at the position indicated, or null if there is a problem. (For the time being there is no delete() method.) The method printArray() has no parameters and prints the contents of the array in physical
order. This is to be used for debugging only.



The author's
code BinaryTreeWithLNRTraversal (RENAMED BinarySearchTree) is on WebCT. Modify this code to make a tree that holds (only) a partNumber and an index to the AutoPart object of which that is the ID number.

· When a AutoPart object
is inserted into DataBank, its partNumber is inserted into the tree, along with its index (where the object
is in the array).

· When a AutoPart object
is searched for, it is found by finding its partNumber in the tree and using the
index to find the object in the array. (If you just search down the array you
will be penalized.)

· Retain the author's method LNRoutputTraversal(), which you may need for debugging.

· Add a method printParts()
based on LNRoutputTraversal() that prints all
of the parts in ascending partNumber
order.



Modify the class
PartsStore from the previous
assignment to store AutoPart
objects in a BMinusTree.
(Don't write a separate driver; PartsStore is the driver.) For
simplicity we will allow updates to the price and numberInStock
fields only. Be sure that PartsStore
exercises the BMinusTree
thoroughly. I reserve the right to replace your PartsStore class with my own test class.



Submission:

Every file that
you submit must begin with a comment giving the author's name. If you modify
someone else's file, include both the original author's name and your name.



Submit the files AutoPart, DataBank, BinarySearchTree, and PartsStore on
WebCT by the date and time specified above. If you cannot submit on WebCT email
the files to me. Submit only .java files,
not .class files. Do not use a Java
package. Do not put the files into a folder or, zip the files or use any other
archive.