Develop a Java Package

Term Project

CS 2210 – Fall 2009

David Riggleman

Abraham Vivas

I. Requirements: Develop a Java package which implements an ADT for a (2,4) search tree.

1. Your ADT should be able to store ordered information, and be accessed according to the Dictionary interface (i.e., it should implement the dictionary interface).
2. You should design your ADT such that is can store any Object.
3. Your ADT should be thoroughly tested and well commented.

II. Design: In planning what to do for this project, we first looked at each of the methods that we needed to implement and came up with a general idea of how we would code each of them. We then started by creating helper functions that would be used in multiple methods, both in the insertElement and removeElement. After writing the helper functions, we worked on the insertElement method, since we needed to be able to correctly insert into the tree before we could begin working on the removeElement method. Finally, we worked on the removeElement method, splitting up the tasks so one of us worked on the fusions and the other worked on the transfers.

III. Implementation: To implement the design, we first had the helper functions. The first helper method was the findIndexOfGreaterOrEqual. This method was used to find and insert elements as it returned the location of where to insert the new element.  Another method, findChildIndex, however was necessary when dealing with duplicates in the tree and found the index in the parent corresponding with the child node, which was necessary when dealing with overflow and underflow. The final main helper method was findNode, which returned the node where the object key was found. As a result, the findElement method specified by the Dictionary interface simply involved finding the node with this subroutine, finding the index with the first helper method and then returning the element with the returned index.  For the insertElement method, the steps include finding the insert location, adding the new item, and then checking for underflow, which is when a node has too many items, which is four in a 2-4 tree.  If an underflow occurred, we called the overflow method, which fixed the tree by splitting the node by moving the third item up to the parent node.  Finally, the removeElement was most complicated. If the node was external, then you could remove it there. If the node was internal, then you have to find the inorder successor and swap it with the item you want to remove. In both cases, you have to check whether underflow occurred, where a node does not have any items. If this happens, we call the underflow method, which fixes the tree by either doing a fusion (merging two nodes each with one item into one node) or a transfer (moving an element from the node with more than more item to the parent and then moving the item in the parent to the node that has no items.