At Home Programming Assignment 5 - 2-3 Tree

Due Wednesday, March 16 at 8 PM (you may not turn this project in late but you can still get early extra credit points)

In this assignment, you will be implementing a 2-3 tree to handle the DVD database of a video store. Nodes will store the titles of the DVDs. The title will be stored as a string and titles may consist of multiple words. Include AT LEAST the following functions for your 2-3 tree. For each operation I have included the function prototype that you must use so that your tree will interface with the main test file. This is by no means an exhaustive list of the functions that you will be writing.

Print the tree in the following manners. When printing a value, print the string followed by a , and 1 space. You must follow these guidelines exactly! For example: Aliens, The Lord of the Rings, Kill Bill,
- void preOrder ( ) - Traverse and print the tree in preorder notation following the printing guidelines specified above.
- void inOrder ( ) - Traverse and print the tree in inorder notation following the printing guidelines specified above.
- void postOrder ( ) - Traverse and print the tree in postorder notation following the printing guidelines specified above.
void insert ( string ) - Insert an item into the 2-3 tree. Be sure to maintain the 2-3 tree properties.
void remove ( string ) - Remove a specified item from the tree. Be sure to maintain the 2-3 tree properties. Some removes can be resolved in multiple ways. To make sure that your output matches mine exaclty, follow the examples listed in the notes below. If an ambiguous case arrises that I have not specified, ask me and I will make the specification.
Node* search ( string ) - Search for a specified item in the tree. Return a pointer to the node containing the item if the time exists in the tree. Return null if the item does not exist.

Provided files

The following skeleton code has been provided. You will need to add your own member functions and variables to the classes.

node.h contains the node class definition. You may add additional variables and functions to this class but you MAY NOT add another Node* or another string variable. You will lose points if you add either of these variables.
tree.h
main.cc - Main function used for testing your final turnin. If your program does not interface with this main file EXACTLY, your assignment may not be graded
sample.out - Output for main.cc. Your output must match EXACTLY. Run a diff on your output and mine to make sure that there are no differences. If your output does not match EXACTLY, you may lose points.

Provided notes

For the majority of the main testing cases, I have provided notes that illustrate what the tree is doing exactly. These notes will show you how to perform inserts and removes that can be resolved in multiple ways. You must follow the illustrations in these notes exactly or else your output will not match mine. Notice that I did not write out the complete titles for each movie in the tree. Instead, each movie has been assigned a letter to represent that movie. You can look at the top of main.cc for letter to movie substitutions.

Notes for tests 1 through 7 - Page 1
Notes for tests 8 through 15 - Page 1b, Page 2b
Notes for tests 16 through 21 - Page 1, Page 2, Page 3 Page 4
Notes for tests 22 through 25 - Page 1c

Extra credit opertunity

You will be given the opertunity to earn up to 10% extra credit on this assignment for implementing the more difficult remove cases. To be eligible for extra credit you must have a readme file stating that you have completed the extra credit (if you don't tell us, we won't grade you for extra credit). For the extra credit, we will test your program with main_ec.cc and the output must match sample_ec.out exactly.

Suggestions to follow while coding

It is very important for you to follow a modular programming style for this assignment. Write a functions for anything and everything that can be easily and logically grouped into a function.

Grading

If you complete tests 1-15, you can achieve at most 80 out of 100 points on this assignment. Make sure you have at least these test cases working before moving one. The more difficult tests in test cases 16-25 will get you the remaining 20 points for the assignment

Testing

We will grade your programming using this main.cc file. This means, the first thing that we will do when grading is delete your main.cc and replace it with ours. DO NOT put any code necessary for correct operation of your program in your main.cc file. The output of your program must look EXACTLY like sample.out. This means that you need to do a diff between our sample output and your actual output to determine if your program will pass our testing (do a man on diff to read about it). Be advised, that if your output does not look EXACTLY like our output, you will lose points. This means that diff would output nothing when comparing our sample output to your sample output.

What to turn in

You should have turned in what you have thus far on our program at least 6 hours before the due date (by 2pm). Then continue to work on your program and turn in more current versions as you get them working. Ideally, you should have your project done well before the due date.

You must turn in all .cc and .h files and your makefile. In addition, you must follow any guidelines and include any information that is stated on the main page about at-home programming assignments. You must include a readme file stating which test cases work and which do not.

DO NOT, I repeat, DO NOT turn in any files that are not required for the final compilation of your assignment. Do not turn in your temporary .cc files or your saved/olded revisions of your .cc files. If you turn in files that aren't required for your assignment, it hinders the grading processes. You will be docked points if you turn in extraineous files.

A reminder about collaboration on home programming assignments

Please remember, at-home programming assignments are not lab assignments and you may not team-code with your lab partner or any other individual. Limited collaboration may be acceptable, but programs must represent YOUR OWN original work. Sharing code or team-coding are strictly not allowed. Copying code from ANY source (any book, current or past students, past solutions, web, etc) is strictly not allowed even with citation. Collaboration may consist of discussing the general approach to solving the problem, but should not involve communicating in code or even pseudo-code. Students may help others find bugs. Your code MUST be unique -- the odds of randomly producing similar code is very low. Computing, like surgery or driving a car or playing golf, can only be learned by doing it yourself!