with particular keyinsert new item into the nodemoving existing items if necessaryand remove an itemagain moving existing items if necessary don' confuse these methods with the find(and insert(routines in the tree classwhich we'll look at next display routine displays node with slashes separating the data itemslike /// / /or / don' forget that in javareferences are automatically initialized to null and numbers to when their object is createdso class node doesn' need constructor the tree class an object of the tree class represents the entire tree the class has only one fieldrootof type node all operations start at the rootso that' all tree needs to remember searching searching for data item with specified key is carried out by the find(routine it starts at the rootand at each node calls that node' finditem(routine to see if the item is there if soit returns the index of the item within the node' item array if find(is at leaf and can' find the itemthe search has failedso it returns - if it can' find the item in the current nodeand the current node isn' leaffind(calls the getnextchild(methodwhich figures out which of node' children the routine should go to next inserting the insert(method starts with code similar to find()except that if it finds full node it splits it alsoit assumes it can' failit keeps lookinggoing to deeper and deeper levelsuntil it finds leaf node at this point it inserts the new data item into the leaf (there is always room in the leafotherwise the leaf would have been split splitting the split(method is the most complicated in this program it is passed the node that will be split as an argument firstthe two rightmost data items are removed from the node and stored then the two rightmost children are disconnectedtheir references are also stored new nodecalled newrightis created it will be placed to the right of the node being split if the node being split is the rootan additional new node is createda new root nextappropriate connections are made to the parent of the node being split it may be pre-existing parentor if the root is being split it will be the newly created root node assume the three data items in the node being split are called aband item is inserted in this parent node if necessarythe parent' existing children are disconnected and reconnected one position to the right to make room for the new data item and new connections the newright node is connected to this parent (refer to figures and now the focus shifts to the newright node data item is inserted in itand child and child which were previously disconnected from the node being splitare connected to it the split is now completeand the split(routine returns