Computer Science 282 Advanced Data Structures Programming Project #2 234 Trees and B Trees (10 Points) For this project, we are going to start with code from the textbook and build on top of it. In chapter 10 there is a fully functional 234 Tree program example, but it has several limitations. It does not store the tree to a disk drive and it does not support building B-Trees. For this project, you will add the disk storage capability, use Inheritance and code to support B-Trees. Keep in mind, one very important goal of this project. Change the existing code from the book as little as possible! Do not rewrite the code. Develop the code as a new 'layer' of code. Use OOP Inheritance to build new classes from the existing classes. For example, when you add BTree support, write a new split() method in the new derived class, DO NOT modify the old one. In fact, keep it as part of the code so the program will support BOTH a BTree and a 234 Tree. Phase 1 Load, compile and run the chapter 10 code from the textbook. You can acquire the code from the books web site or you can use the week 8 notes for this class. I would suggest a few minor changes to this code. Change or rename the file from tree234.java to Tree234App.java. Change the line ' class Tree234App ' to ' public class Tree234App ' Add one more command to the menu, 'q' to quit the program Remove the final from the variable ORDER (bad for inheritance) Add your own comments to the top, listing your name, date, class and project info. Also explain the code in the file. Every .java file should have these comments at the top. At this point you should be able to compile and run the command line program. Building a 234 tree, displaying, inserting and finding items in that tree. The book jams multiple classes into one '.java' file, a poor programming practice. Create a new '.java' file for EACH class and 'cut and paste' the appropriate class into that file. Remember, the name of the file should exactly match the name of the class and each class should be declared 'public'. Phase 2 The 234 Tree code is written in such a way that it can be upgraded to a B-Tree. With a new version of split() this upgrade can be done with very few changes to the code. However, you are going to have to be clever to do this in a way that DOES NOT break the rest of the code. Make sure the new version of split() is in a subclass. Leave the old version unchanged in the super class. Add a new '.java' file to your project, in that file create a new class named 'BTree' using inheritance to create it from the class 'Tree234'. Copy and paste the split() method from the parent class to the child class. Got that? There will be two split() methods! You may change the 'root' access permission to protected, but DO NOT change it to public. Add a new command to the menu, 'c' to change the ORDER of the tree. You will need to add a static method setOrder() to the Node class and call this method BEFORE you create a new tree object. When the user enters an ORDER equal to 4 a new Tree234 object is created, when the ORDER is 5 or larger a new BTree object is created. Reuse the variable that references the tree object created at the top of the main method. DO NOT declare a new reference variable. Since the BTree class inherits from Tree234 you can assign a BTree object to a variable of type Tree234. Think about how you can test your code! Notice how the code at the top of main() creates a default tree AND populates the tree with values. Great idea, no need to insert a bunch of values to test your code. When you create a new tree make sure you populate the tree with values. Speaking of testing, BEFORE you change the BTree split() method you can test your program. At this point, the program should run, the default tree should still be a Tree234 object and work as it did in Phase 1. You can NOW change the ORDER to 5 or greater and create a BTree object. Did you populate the tree? Since the split() method has not been changed the algorithm will still only MOVE one item to the new Node. That's OK, still a BTree, you can show, insert and find on this NEW BTree object. Look closely after a split(), you will see that it only moves 1 item to the new Node, even when it 'should' move 2 or more items. After you test your code with the 'old' split() method it is time to modify the 'new' split() method in the class BTree to behave more like a BTree split. It is enough, to make the Btree split() move multiple items (and their child references) to the new node. The larger the ORDER, the more items need to move. You do not need to change the split node algorithm to go 'bottom' up. Go ahead and split the nodes on the way down just like with a 234 tree. You do not need to insert the item BEFORE the spilt. Go ahead and insert the item AFTER the split just like with a 234 tree. Of the three major differences between the 234 and BTree split(), the only one you need to implement is moving multiple items (and their child references) to the new node. For example, when ORDER = 4, there will be 3 items in the node when a split occurs: A B C In this case, Tree234 split must move one item ( C ) to the new node For example, when ORDER = 6, there will be 5 items in the node when a split occurs: A A B C C In this case, Btree split must move two items ( C C ) to the new node For example, when ORDER = 7, there will be 6 items in the node when a split occurs: A A A B C C In this case, Btree split must move two items ( C C ) to the new node For example, when ORDER = 8, there will be 7 items in the node when a split occurs: A A A B C C C In this case, Btree split must move three items ( C C C ) to the new node You will need to calculate the number of items to MOVE, based on the ORDER of the tree. Do not hard code values like 8 or 7 or 3 in your code, do the simple math. Be sure to TEST! Populate the tree with items so it is just before or just after the split. You do NOT want to have to insert a bunch of items to get to the split. Add print statements so it displays the number of item and values it will move. Obviously, when you move items to the new Node, plus one child references should move with the items. If you move three items ( C C C ) to the new Node, four child references move with those three items. Phase 3 Below is a link to a plain text file that contains users. This file contains 1000 randomly generated users, each line has the format: user ID, email address, first name, last name, text color, background color Here is the link: data2.txt ( right click ) Right Click on the link and do a Save as... to your disk with the name 'data2.txt' Add a Read command to your program, with the letter 'r' on your menu to allow the user to read a data file. Notice the user ID that is at the start of each record. This will be our key, and will be the dData value stored in the DataItem object. You will need to add a String variable named 'record' to the DataItem class, and add methods that allow you to set and get its value. Each DataItem will contain 2 variables, dData and a string with the enitire record. When you read the file and create each DataItem object, both values must be set. When the user enters 'r' to read, call a method named 'readData' that does the following: #1 Ask them the name of the text file to import. #2 Print the current order of the tree and ask the 'Y'es or 'N'o do you want to change the order. #3 If 'Y'es, ask them for the new order of the tree. #4 Build a BTree in memory out of the data read from the named text file. For now, when you display the tree, just show the dData, do NOT show the remainder of the record. Always make it easy to test your software when you are developing 'new' code. While you are testing, you DO NOT want to have to do 4 or 5 keyboard inputs to test your code to read the data file. Write a small method named 'testreadData' that will hard code a filename and order so you can test with no extra keyboard input. When you are testing you can have your program immediately call 'testreadData' so there is NO NEED to input a bunch of data. I might even have it display the tree automatically so I don't even have to type in that command. When the code is fully working, then change it so the 'r' command calls the proper method: 'readData' Another testing/developing hint. You DO NOT have read the entire 'data2.txt' file when you are testing your code. Create a few small test files with a limited number of records. Perhaps just enough to cause a split to occur. Make sure your 'testreadData' uses one of your small test case files. Trying to debug code when the tree has 10 DataItems is a LOT easier than debugging a tree with a 1000 DataItems.