begin such an operation by performing search in for an entry with key removing such an entry from ( , tree can always be reduced to the case where the entry to be removed is stored at node whose children are external nodes supposefor instancethat the entry with key that we wish to remove is stored in the ith entry ( , at node that has only internal-node children in this casewe swap the entry ( , with an appropriate entry that is stored at node with external-node children as follows (see figure ) we find the right-most internal node in the subtree rooted at the ith child of znoting that the children of node are all external nodes we swap the entry ( at with the last entry of once we ensure that the entry to remove is stored at node with only externalnode children (because either it was already at or we swapped it into )we simply remove the entry from (that isfrom the dictionary ( )and remove the ith external node of removing an entry (and childfrom node as described above preserves the depth propertyfor we always remove an external node child from node with only external-node children howeverin removing such an external node we may violate the size property at indeedif was previously -nodethen it becomes -node with no entries after the removal (figure and )which is not allowed in ( , tree this type of violation of the size property is called an underflow at node to remedy an underflowwe check whether an immediate sibling of is -node or -node if we find such sibling wthen we perform transfer operationin which we move child of to va key of to the parent of and wand key of to (see figure and if has only one siblingor if both immediate siblings of are -nodesthen we perform fusion operationin which we merge with siblingcreating new node 'and move key from the parent of to (see figure and fusion operation at node may cause new underflow to occur at the parent of vwhich in turn triggers transfer or fusion at (see figure hencethe number of fusion operations is bounded by the height of the treewhich is (lognby proposition if an underflow propagates all the way up to the rootthen the root is simply deleted (see figure and we show sequence of removals from ( , tree in figures and figure sequence of removals from ( , tree(aremoval of causing an underflow(ba transfer operation(cafter the transfer operation(dremoval of causing an underflow(ea fusion