chap indexing figure simple node-splitting insert for - tree the value is added to the - tree of figure this makes the node containing values and splitpromoting value to the parent node with the middle of the three key value is passed up to the parent node along with pointer to this is called promotion the promoted key is then inserted into the parent if the parent currently contains only one record (and thus has only two children)then the promoted record and the pointer to are simply added to the parent node if the parent is fullthen the split-and-promote process is repeated figure illustrates simple promotion figure illustrates what happens when promotions require the root to splitadding new level to the tree in either caseall leaf nodes continue to have equal depth figures and present an implementation for the insertion process note that inserthelp of figure takes three parameters the first is pointer to the root of the current subtreenamed rt the second is the key for the record to be insertedand the third is the record itself the return value for inserthelp is pointer to - tree node if rt is unchangedthen pointer to rt is returned if rt is changed (due to the insertion causing the node to split)then pointer to the new subtree root is returnedwith the key value and record value in the leftmost fieldsand pointer to the (singlesubtree in the center pointer field this revised node will then be added to the parentas illustrated in figure when deleting record from the - treethere are three cases to consider the simplest occurs when the record is to be removed from leaf node containing two records in this casethe record is simply removedand no other nodes are affected the second case occurs when the only record in leaf node is to be removed the third case occurs when record is to be removed from an internal node in both the second and the third casesthe deleted record is replaced with another that can take its place while maintaining the correct ordersimilar to removing node from bst if the tree is sparse enoughthere is no such record available that will allow all nodes to still maintain at least one record in this situationsibling nodes are merged together the delete operation for the - tree is excessively complex and will not be described further insteada complete discussion of deletion will be