CS 146: Homework due 3/24

Programming assignment: Consider 2-3 trees, as discussed in class. You are to implement this data structure. You will need to allow for insertions, and also for searches as described below. You will not need deletions. (For notes on how to get input, you may use: Java Input Notes, but you do not need to.)

Input: The first line of program input will contain a single number n < 100. This will be the number of values of input for this tree. The second line will contain n distinct integer values, each between -1000 and 1000. Each value should be inserted into a 2-3 tree (starting with an empty one) in order. Each line after that will contain an integer which should be interpreted as a search operation for that number. At the end of input, your program should exit.
Output: Upon searching for value x in your 2-3 tree, if the value is not in the tree, your search for it should terminate in a leaf node of your tree. In this case, your output should be the integer contents of that leaf. If there are two keys in that leaf, first print the smaller value, then the larger, with a single space separating them. If there is only one key value, simply print that single value. For each search item, the output should take one line.
If the value x is found in the tree, print the contents of its node, using the same format as above.
Example: Consider the 5 line input:
5
1 2 4 5 6
1
2
3
You should get the 3 line output as follows:
1
2 5
4
Because, after inserting (in order) values 1, 2, 4, 5, 6:
1 would be in a leaf by itself
2 would be in the tree (in this case the root), in a node with value 5
3 is not in the tree, but in searching for it you should end up in the leaf with value 4.

Note: both the input and output format are precisely specified for the problem. If you assume a different input format, your program may or may not work correctly. If you give a different output, your solution will be rejected. Do not add extra spaces, do not make any assumptions not in the problem specification. I will be automating the testing of your programs, and the automated system will not be very forgiving. It should not take great effort for me to get your code to run.

You need to submit your solutions to me. You should email them to me with the following subject line: "CS146Spring06: Program 2 TaylorDS", without the quotes, and where TaylorDS is replaced by Your last name and initials. The email should be empty, other than an attached file of source code, in a single text file named "prog2.java" (no quotes). I should be able to compile it, and run it on a test case of my own with no fuss. Please follow these directions carefully, as the process will be (hopefully) automated. I will allow you to use any fairly recent version of Java.

Your program is officially due 3/24. I will not assign homework for over the break, I think it is best to take a break. On the other hand, I know that many of you are very busy just before break and rather than "forcing" you to take a break from my class, I will accept this program, without penalty, for one extra week (until 3/31). This only forces a one weekend break.