in either case, after making this change to the tree structure, it is necessary to rebalance the tree and update its ranks. as in the case of an insertion, this may be done by following a path upwards in the tree and changing the ranks of the nodes along this path until one of three things happens: the root is reached and the tree is balanced, a node is reached whose rank does not need to be changed, and again the tree is balanced, or a node is reached whose rank cannot be changed. in this last case a constant number of tree rotations completes the rebalancing stage of the deletion process.