Class TwoThreeTreeClass

java.lang.Object

p8_package.TwoThreeTreeClass

- Students will review the development of a basic data type that incorporates the use of linked data for management

- Students will review use of Java arrays, and practice basic algorithmic activities with linked data

- Students will review the pass-by-copy practice of Java, along with managing potential aliasing issues in method development

- Students will practice development, implementation, and usage of supporting/utility methods

- Students will generate classes that manage data in the form of a self-balancing tree structure

- Students will practice implementing methods in such a way that code is rarely, if ever, repeated by implementing supporting or utility methods in their development activities

- Students will demonstrate analytic and diagnostic competence with testing and verifying all components of the given assignment

Class should have this following parts

Field Summary

Modifier and Type	Field and Description

private int

LEFT_CHILD_SELECT

constant used in constructor to indicate which child to create - Left

private int

ONE_DATA_ITEM

constant used for identifying one data item stored

private java.lang.String

outputString

Used for acquiring ordered tree visitations in String form

private int

RIGHT_CHILD_SELECT

constant used in constructor to indicate which child to create - Right

private TwoThreeTreeClass.TwoThreeNodeClass

root

root of tree

private int

THREE_DATA_ITEMS

constant used for identifying three data items stored

private int

TWO_DATA_ITEMS

constant used for identifying two data items stored

Method Summary

Modifier and Type	Method and Description
private void	addAndOrganizeData(TwoThreeTreeClass.TwoThreeNodeClass localRef, int itemVal) Method is called when addItemHelper arrives at the bottom of the 2-3 search tree (i.e., all node's children are null);
void	addItem(int itemVal) Adds item to 2-3 tree using addItemHelper as needed
private void	addItemHelper(TwoThreeTreeClass.TwoThreeNodeClass parRef,TwoThreeTreeClass.TwoThreeNodeClass localRef, int itemVal) Helper method searches from top of tree to bottom using divide and conquer strategy to find correct location (node) for new added value; once location is found, item is added to node using addAndOrganizeData and then fixUpInsert is called in case the updated node has become a three-value node
void	clear() Method clears tree so that new items can be added again
private TwoThreeTreeClass.TwoThreeNodeClass	copyConstructorHelper(TwoThreeTreeClass.TwoThreeNodeClass workingCopiedRef) Implements tree duplication effort with recursive method; copies data into newly created nodes and creates all new references to child nodes
private void	fixUpInsert(TwoThreeTreeClass.TwoThreeNodeClass localRef) Method used to fix tree any time a three-value node has been added to the bottom of the tree; it is always called but decides to act only if it finds a three-value node
private boolean	foundInNode(TwoThreeTreeClass.TwoThreeNodeClass localRef, int searchVal) Tests center value if single node, tests left and right values if two-value node; returns true if specified data is found in any given node
java.lang.String	inOrderTraversal() Public method called by user to display data in order
private void	inOrderTraversalHelper(TwoThreeTreeClass.TwoThreeNodeClass localRef) Helper method conducts in order traversal with 2-3 tree
boolean	search(int searchVal) Search method used by programmer to find specified item in 2-3 tree
private boolean	searchHelper(TwoThreeTreeClass.TwoThreeNodeClass localRef, int searchVal) Search helper method that traverses through tree in a recursive divide and conquer search fashion to find given integer in 2-3 tree Node class to be used for the TwoThreeTree class (internally): /** * 2-3 node class using NodeDataClass data and three references * * @author MichaelL */ private class TwoThreeNodeClass { /** * internal 2-3 node data */ private int leftData, centerData, rightData, numItems; /** * references from 2-3 node */ private TwoThreeNodeClass leftChildRef, centerChildRef, rightChildRef; /** * references for managing 2-3 node adjustments */ private TwoThreeNodeClass auxLeftRef, auxRightRef; /** * parent reference for 2-3 node */ private TwoThreeNodeClass parentRef; /** * Default 2-3 node class constructor */ private TwoThreeNodeClass() { leftData = centerData = rightData = numItems = 0; leftChildRef = centerChildRef = rightChildRef = null; auxLeftRef = auxRightRef = parentRef = null; } /** * Initialization 2-3 node class constructor * * @param centerIn integer data sets first node initialization */ private TwoThreeNodeClass( int centerIn ) { centerData = centerIn; leftData = rightData = 0; numItems = 1; leftChildRef = centerChildRef = rightChildRef = null; auxLeftRef = auxRightRef = parentRef = null; } /** * Private constructor used to create new left or right child node * of given parent with the children linked from * a current three-node object * * @param childSelect integer selection value that informs * the constructor to create a left or a right child * along with making all the sub-child links; * uses class constants LEFT_CHILD_SELECT and RIGHT_CHILD_SELECT * * @param localRef TwoThreeNodeClass reference * with three-node data and associated references * * @param parRef TwoThreeNodeclass parent reference * for linking with new left or right child node that is created */ private TwoThreeNodeClass( int childSelect, TwoThreeNodeClass localRef, TwoThreeNodeClass parRef ) { if( childSelect == LEFT_CHILD_SELECT ) { this.centerData = localRef.leftData; this.leftChildRef = localRef.leftChildRef; this.rightChildRef = localRef.auxLeftRef; if( leftChildRef != null ) { this.leftChildRef.parentRef = this; this.rightChildRef.parentRef = this; } } else // assume right child select { this.centerData = localRef.rightData; this.leftChildRef = localRef.auxRightRef; this.rightChildRef = localRef.rightChildRef; if( rightChildRef != null ) { this.leftChildRef.parentRef = this; this.rightChildRef.parentRef = this; } } this.leftData = this.rightData = 0; this.numItems = 1; this.centerChildRef = null; this.auxLeftRef = this.auxRightRef = null; this.parentRef = parRef; } /** * Copy 2-3 node class constructor * * Note: Only copies data; does not copy links * as these would be incorrect for the new tree * (i.e., they would be related to the copied tree) * * @param copied TwoThreeNodeClass object to be copied */ private TwoThreeNodeClass( TwoThreeNodeClass copied ) { leftData = copied.leftData; centerData = copied.centerData; rightData = copied.rightData; numItems = copied.numItems; leftChildRef = centerChildRef = rightChildRef = null; auxLeftRef = auxRightRef = parentRef = null; } } Rubric - PA08 Program builds correctly, no errors or warnings: +5 SetClass methods are developed correctly: +35 default constructor (TwoThreeTreeClass) (+2) copy constructor/helper (TwoThreeTreeClass) (+5) addAndOrganizeData (+5) addItem/helper (+5) clear (+2) fixUpInsert (+5) foundInNode (+3) inOrderTraversal/helper (+3) search/helper (+5) All other specifications followed: +5 correct file upload correct method names, variable names, etc. appropriate use of constant (final) value Appropriate Javadoc documentation with each method: +5 @param, @return correctly used notes with correctly used as dividers Javadoc output is not required at this point General Usage Rubric reductions see GUR document