The delete algorithm is very similar to the insert, just a little more complicated. It also requires that we use the basic ideas from the find algorithm to locate the proper leaf, then remove (in this case) the item, and readjust the keys in the leaf.

Now, however, it is possible that the leaf is less than half full. It must work with its siblings to restore the structure of the tree. If it has a sibling with extra keys, a key can be moved from one leaf to the next (with the appropriate changes in the parent node).

On the other hand, if the sibling doesn't have any keys to spare, then the two nodes must be merged. This will obviously require that the parent node give up a key (since it no longer has to distinguish between the two leaves). This might make the parent too small as well, and necessitate further consolidation up the chain. But again the cost is at worst O(log n).