notes if node underflowswe may be able to "redistributekeys by borrowing some from neighboring node for examplein the order -tree belowthe key is being deletedwhich causes node to underflow since it only has keys and left so keys from the neighbor on the left are "shifted throughthe parent node and redistributed so both leaf nodes end up with keysbefore deleting after deleting xx xx ++ [ [ xx xx ++ [ [ but if the underflow node and the neighbor node have less than keys to redistributethe two nodes will have to be combined for examplehere key is being deleted from the -tree belowcausing an underflowand the neighbor node can' afford to give up any keys for redistribution so one node is discardedand the parent key moves down with the other keys to fill up single nodebefore deleting after deleting -+++--- [ [ -+ [ in the above casemoving the key out of the parent node left two keys ( and remaining but if the parent node only had keys to begin withthen the parent node also would underflow when the parent key was moved down to combine with the leaf key indeedunderflow and the combining of nodes may propagate all the way up to the root node when the root underflowsthe -tree shrinks in height by one leveland the nodes under the old root combine to form new root the payoff of the -tree insert and delete rules are that -trees are always "balancedsearching an unbalanced tree may require traversing an arbitrary and unpredictable number of nodes and pointers an unbalanced tree of nodes balanced tree of nodes ++ searching balanced tree means that all leaves are at the same depth there is no runaway pointer overhead indeedeven very large -trees can guarantee only small number of nodes must be retrieved to find given key for examplea -tree of , , keys with keys per node never needs to retrieve more than nodes to find any key lovely professional university