trees and external storage we've chosen to store the number of items currently in the node (numitemsand the node' parent (parentas fields in this class neither of these fields is strictly necessary and could be eliminated to make the nodes smaller howeverincluding them clarifies the programmingand only small price is paid in increased node size various small utility routines are provided in the node class to manage the connections to child and parent and to check if the node is full and if it is leaf howeverthe major work is done by the finditem()insertitem()and removeitem(routineswhich handle individual items within the node they search through the node for data item 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 root and at each node calls that node' finditem(routine to see whether 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 it splits full node if it finds one alsoit assumes it can' failit keeps lookinggoing to deeper and deeper levelsuntil it finds leaf node at this point the method inserts the new data item into the leaf (there is always room in the leafotherwisethe 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