-trees -tree implementation looking up value in -tree is relatively simple and is left as an exercise for the reader inserting and deleting values are where all the action is alan tharp [ provides great discussion of both inserting and deleting values in -tree in this text we provide new examples and suggest both iterative and recursive implementations of both operations -tree insert inserting an item in -tree involves finding the leaf node which should contain the item it may also involve splitting if no room is left in the leaf node when leaf node reaches its capacitywhich is two times its degree and new item is being insertedthe *degree+ items are sorted and the median value ( the middle valueis promoted up the tree to the parent node in this waysplitting may cascade up the tree to see the splitting process in actionconsider building the tree given in fig with the keys given in this order [ the first item to be inserted is the when this occursthe -tree is emptyconsisting of one empty node the ( , item is added into that node as shown in fig the items with keys and are inserted in similar fashion as shown in fig the node is now full the next item to be inserted will cause split the next item inserted is causing the node to split into two nodes the left subtree node is the original node the right subtree contains the new node the middle value in this caseis promoted up to the parent in this casethere is no parent since we split the root node in this special case new root node is created to hold the promoted value after taking these stepsthe tree appears as shown in fig the three values and are inserted resulting in the tree as shown in fig when is inserted -tree node number is going to split and promote the middle value in this caseup to the parent this time there is room in the parent so the new item is added resulting in the tree shown in fig fig inserting into an empty -tree fig after inserting and this copy belongs to 'acha