overall, as with the insertion procedure, a deletion consists of a search downward through the tree (to find the node to be deleted), a continuation of the search farther downward (to find a node with an external child), the removal of a constant number of new nodes, a logarithmic number of rank changes, and a constant number of tree rotations.