inserting new item notes when inserting an itemfirst do search for it in the -tree if the item is not already in the -treethis unsuccessful search will end at leaf if there is room in this leafjust insert the new item here note that this may require that some existing keys be moved one to the right to make room for the new item if instead this leaf node is full so that there is no room to add the new itemthen the node must be "splitwith about half of the keys going into new node to the right of this one the median (middlekey is moved up into the parent node (of courseif that node has no roomthen it may have to be split as well note that when adding to an internal nodenot only might we have to move some keys one position to the rightbut the associated pointers have to be moved right as well if the root node is ever splitthe median key moves up into new root nodethus causing the tree to increase in height by one insert the following letters into what is originally an empty -tree of order order means that node can have maximum of children and keys all nodes other than the root must have minimum of keys the first letters get inserted into the same noderesulting in this picturea when we try to insert the hwe find no room in this nodeso we split it into nodesmoving the median item up into new root node note that in practice we just leave the and in the current node and place the and into new node to the right of the old one inserting ekand proceeds without requiring any splitsg inserting requires split note that happens to be the median key and so is moved up into the parent node lovely professional university