analysis of insertion in ( , tree because dmax is at most the original search for the placement of new key uses ( time at each leveland thus (log ntime overallsince the height of the tree is (log nby proposition the modifications to single node to insert new key and child can be implemented to run in ( timeas can single split operation the number of cascading split operations is bounded by the height of the treeand so that phase of the insertion process also runs in (log ntime thereforethe total time to perform an insertion in ( tree is (log ndeletion let us now consider the removal of an item with key from ( tree we begin such an operation by performing search in for an item with key removing an item from ( tree can always be reduced to the case where the item to be removed is stored at node whose children are external nodes supposefor instancethat the item with key that we wish to remove is stored in the ith item (ki vi at node that has only internal-node children in this casewe swap the item (ki vi with an appropriate item that is stored at node with external-node children as follows (see figure ) we find the rightmost internal node in the subtree rooted at the ith child of znoting that the children of node are all external nodes we swap the item (ki vi at with the last item of once we ensure that the item 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 item from and remove the ith external node of removing an item (and childfrom node as described above preserves the depth propertyfor we always remove an external child from node with only external children howeverin removing such an external nodewe may violate the size property at indeedif was previously -nodethen it becomes -node with no items 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 sthen we perform transfer operationin which we move child of to wa key of to the parent of and sand 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