Please solve this question using the main method provided below and remeber that you MUST get the same output that is here too. Thank you very much

Modify the tree234.java program (Listing 10.1) so that it creates and works with 2-3 trees instead. It should display the tree and allow searches. It should also allow items to be inserted, but only if the parent of the leaf node (which is being split) does not also need to be split. This implies that the split() routine need not be recursive. In writing insert(), remember that no splits happen until the appropriate leaf has been located. Then the leaf will be split if its full. Youll need to be able to split the root too, but only when its a leaf. With this limited routine you can insert fewer than nine items before the program crashes.

LISTING 10.1

// tree234.java // demonstrates 234 tree // to run this program: C>java Tree234App import java.io.*; //////////////////////////////////////////////////////////////// class DataItem {

public long dData; // one data item //-------------------------------------------------------------- public DataItem(long dd) // constructor { dData = dd; } //-------------------------------------------------------------- public void displayItem() // display item, format /27 { System.out.print(/+dData); } //-------------------------------------------------------------- } // end class DataItem //////////////////////////////////////////////////////////////// class Node { private static final int ORDER = 4; private int numItems; private Node parent; private Node childArray[] = new Node[ORDER]; private DataItem itemArray[] = new DataItem[ORDER-1]; // ------------------------------------------------------------- // connect child to this node public void connectChild(int childNum, Node child) { childArray[childNum] = child; if(child != null) child.parent = this; } // ------------------------------------------------------------- // disconnect child from this node, return it public Node disconnectChild(int childNum) { Node tempNode = childArray[childNum]; childArray[childNum] = null; return tempNode; } // ------------------------------------------------------------- public Node getChild(int childNum) { return childArray[childNum]; } // ------------------------------------------------------------- public Node getParent() { return parent; } // ------------------------------------------------------------- public boolean isLeaf()

{ return (childArray[0]==null) ? true : false; } // ------------------------------------------------------------- public int getNumItems() { return numItems; } // ------------------------------------------------------------- public DataItem getItem(int index) // get DataItem at index { return itemArray[index]; } // ------------------------------------------------------------- public boolean isFull() { return (numItems==ORDER-1) ? true : false; } // ------------------------------------------------------------- public int findItem(long key) // return index of { // item (within node) for(int j=0; j=0; j--) // start on right, { // examine items if(itemArray[j] == null) // if item null, continue; // go left one cell else // not null, { // get its key long itsKey = itemArray[j].dData; if(newKey < itsKey) // if its bigger itemArray[j+1] = itemArray[j]; // shift it right else { itemArray[j+1] = newItem; // insert new item

return j+1; // return index to } // new item } // end else (not null) } // end for // shifted all items, itemArray[0] = newItem; // insert new item return 0; } // end insertItem() // ------------------------------------------------------------- public DataItem removeItem() // remove largest item { // assumes node not empty DataItem temp = itemArray[numItems-1]; // save item itemArray[numItems-1] = null; // disconnect it numItems--; // one less item return temp; // return item } // ------------------------------------------------------------- public void displayNode() // format /24/56/74/ { for(int j=0; j

curNode = getNextChild(curNode, key); } // end while } // ------------------------------------------------------------- // insert a DataItem public void insert(long dValue) { Node curNode = root; DataItem tempItem = new DataItem(dValue); while(true) { if( curNode.isFull() ) // if node full, { split(curNode); // split it curNode = curNode.getParent(); // back up // search once curNode = getNextChild(curNode, dValue); } // end if(node is full) else if( curNode.isLeaf() ) // if node is leaf, break; // go insert // node is not full, not a leaf; so go to lower level else curNode = getNextChild(curNode, dValue); } // end while curNode.insertItem(tempItem); // insert new DataItem } // end insert() // ------------------------------------------------------------- public void split(Node thisNode) // split the node { // assumes node is full DataItem itemB, itemC; Node parent, child2, child3; int itemIndex; itemC = thisNode.removeItem(); // remove items from itemB = thisNode.removeItem(); // this node child2 = thisNode.disconnectChild(2); // remove children child3 = thisNode.disconnectChild(3); // from this node

Node newRight = new Node(); // make new node if(thisNode==root) // if this is the root, { root = new Node(); // make new root parent = root; // root is our parent root.connectChild(0, thisNode); // connect to parent } else // this node not the root parent = thisNode.getParent(); // get parent // deal with parent itemIndex = parent.insertItem(itemB); // item B to parent int n = parent.getNumItems(); // total items? for(int j=n-1; j>itemIndex; j--) // move parents { // connections Node temp = parent.disconnectChild(j); // one child parent.connectChild(j+1, temp); // to the right } // connect newRight to parent parent.connectChild(itemIndex+1, newRight); // deal with newRight newRight.insertItem(itemC); // item C to newRight newRight.connectChild(0, child2); // connect to 0 and 1 newRight.connectChild(1, child3); // on newRight } // end split() // ------------------------------------------------------------- // gets appropriate child of node during search for value public Node getNextChild(Node theNode, long theValue) { int j; // assumes node is not empty, not full, not a leaf int numItems = theNode.getNumItems(); for(j=0; j

return theNode.getChild(j); // return right child } // ------------------------------------------------------------- public void displayTree() { recDisplayTree(root, 0, 0); } // ------------------------------------------------------------- private void recDisplayTree(Node thisNode, int level, int childNumber) { System.out.print(level=+level+ child=+childNumber+ ); thisNode.displayNode(); // display this node // call ourselves for each child of this node int numItems = thisNode.getNumItems(); for(int j=0; j

while(true) { System.out.print(Enter first letter of ); System.out.print(show, insert, or find: ); char choice = getChar(); switch(choice) { case s: theTree.displayTree(); break; case i: System.out.print(Enter value to insert: ); value = getInt(); theTree.insert(value); break; case f: System.out.print(Enter value to find: ); value = getInt(); int found = theTree.find(value); if(found != -1) System.out.println(Found +value); else System.out.println(Could not find +value); break; default: System.out.print(Invalid entry ); } // end switch } // end while } // end main() //-------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //-------------------------------------------------------------- public static char getChar() throws IOException { String s = getString();

return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //------------------------------------------------------------- } // end class Tree234App

You MUST use this main method to solve the question:

public static void main(String[] args) throws IOException

{

long value;

Tree23 theTree = new Tree23();

theTree.insert(10);

theTree.insert(20);

theTree.insert(30);

theTree.insert(30);

theTree.insert(70);

while(true)

{

System.out.print("Enter first letter of ");

System.out.print("show, insert, or find: ");

char choice = getChar();

switch(choice)

{

case 's':

theTree.displayTree();

break;

case 'i':

System.out.print("Enter value to insert: ");

value = getInt();

theTree.insert(value);

break;

case 'f':

System.out.print("Enter value to find: ");

value = getInt();

int found = theTree.find(value);

if(found != -1)

System.out.println("Found " + value);

else

System.out.println("Could not find " + value);

break;

default:

System.out.print("Invalid entry ");

} // end switch

} // end while

} // end main()

You MUST get this output and please when you post the answer make sure to post the output that you get:

Enter first letter of show, insert, or find: s

level=0 child=0 /20/30/

level=1 child=0 /10/

level=1 child=1 /30/

level=1 child=2 /70/

Enter first letter of show, insert, or find: i

Enter value to insert: 5

Enter first letter of show, insert, or find: i

Enter value to insert: 25

Enter first letter of show, insert, or find: s

level=0 child=0 /20/30/

level=1 child=0 /5/10/

level=1 child=1 /25/30/

level=1 child=2 /70/

Enter first letter of show, insert, or find: i

Enter value to insert: 35

Enter first letter of show, insert, or find: s

level=0 child=0 /20/30/

level=1 child=0 /5/10/

level=1 child=1 /25/30/

level=1 child=2 /35/70/

Enter first letter of show, insert, or find: i

Enter value to insert: 80

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2

at Node.insertItem(partial_23.java:92)

at Tree23.split(partial_23.java:189)

at Tree23.insert(partial_23.java:150)

at Tree23App.main(partial_23.java:276)

Process completed.