chap indexing private ttnode inserthelp(ttnode rtkey ke ettnode retvalif (rt =null/empty treecreate leaf node for root return new ttnode(kenullnullnullnullnull)if (rt isleaf()/at leaf nodeinsert here return rt add(new ttnode(kenullnullnullnullnull))/add to internal node if ( compareto(rt lkey() /insert left retval inserthelp(rt lchild()ke)if (retval =rt lchild()return rtelse return rt add(retval)else if((rt rkey(=null|( compareto(rt rkey() )retval inserthelp(rt cchild()ke)if (retval =rt cchild()return rtelse return rt add(retval)else /insert right retval inserthelp(rt cchild()ke)if (retval =rt cchild()return rtelse return rt add(retval)figure the - tree insert routine -trees this section presents the -tree -trees are usually attributed to bayer and mccreight who described the -tree in paper by -trees had replaced virtually all large-file access methods other than hashing -treesor some variant of -treesare the standard file organization for applications requiring insertiondeletionand key range searches -trees address effectively all of the major problems encountered when implementing disk-based search trees -trees are always height balancedwith all leaf nodes at the same level update and search operations affect only few disk blocks the fewer the number of disk blocks affectedthe less disk / is required -trees keep related records (that isrecords with similar key valueson the same disk blockwhich helps to minimize disk / on searches due to locality of reference