to insert the key " "we first simply search for that key if is foundthe key is already in the tree and the insertion is superfluous otherwisewe must end up at leaf node at the bottom level of the tree where would be stored in the above casethe leaf node contains and room for fourth keyso is simply inserted in the leaf node in sorted ordernotes [ now you'll insert the key " the initial search leads us to the leaf node where would be insertedbut the node is already full with keys and adding another key would violate the rule that order -trees can' have more than keys because of this "overflowconditionthe leaf node is split into two leaf nodes the leftmost keys are put in the left nodethe rightmost keys are put in the right nodeand the middle key is "promotedby inserting it into the parent node above the leaf hereinserting causes the - node to be split into two nodesand is moved up to the parent node that contained and before inserting -+ [ after inserting --+-+----+ [ [ in this casethe parent node contained only keys ( and )leaving room for to be promoted and inserted but if the parent node was also already full with keysthen it too would have to split indeedsplitting may propagate all the way up to the root node when the root splitsthe -tree grows in height by one leveland new root with single promoted key is formed ( situation when an order root node sometimes has fewer than keysjust like the situation described earlier when the root node stores the very first key placed in the -tree -trees shrink when keys are deleted to delete keyfirst perform the usual search operation to locate the node containing the key (if the key isn' foundit isn' in the tree and can' be deleted if the found key is not in leafmove it to leaf by swapping the key with the logical "nextkey in -treethe "nextkey is always the first key in the leftmost leaf of the right subtree examplein this -tree we want to delete " "which is not in leaf "xxindicates key values that don' matterxx xx xx +->xx xx xx xx +->xx xx xx xx +->[ you follow the pointer immediately to the right of to find ' right subtreethen follow the leftmost pointers in each subnode until we reach leaf the first key in the leaf is " "the logical "nextkey after in the list of all keys in the tree by swapping and we can move to leaf node to set up deletion without violating the key order or pointer order of the overall -tree once the key we want is in leafwe can delete it if at least keys remain in the nodewe're doneotherwise it is an "underflow"since every node (except the rootmust have at least keys lovely professional university