deletion deleting an item with key from red-black tree initially proceeds as for binary search tree (section structurallythe process results in the removal node that has at most one child (either that originally containing key or its inorder predecessorand the promotion of its remaining child (if anyif the removed node was redthis structural change does not affect the black depths of any paths in the treenor introduce any red violationsand so the resulting tree remains valid red-black tree in the corresponding ( tree this case denotes the shrinking of -node or -node if the removed node was blackthen it either had zero children or it had one child that was red leaf (because the null subtree of the removed node has black height in the latter casethe removed node represents the black part of corresponding -nodeand we restore the redblack properties by recoloring the promoted child to black the more complex case is when (nonrootblack leaf is removed in the corresponding ( treethis denotes the removal of an item from -node without rebalancingsuch change results in deficit of one for the black depth along the path leading to the deleted item by necessitythe removed node must have sibling whose subtree has black height (given that this was valid red-black tree prior to the deletion of the black leaf to remedy this scenariowe consider more general setting with node that is known to have two subtreestheavy and tlight such that the root of tlight (if anyis black and such that the black depth of theavy is exactly one more than that of tlight as portrayed in figure in the case of removed black leafz is the parent of that leaf and tlight is trivially the empty subtree that remains after the deletion we describe the more general case of deficit because our algorithm for rebalancing the tree willin some casespush the deficit higher in the tree (just as the resolution of deletion in ( tree sometimes cascades upwardwe let denote the root of theavy (such node exists because theavy has black height at least one tlight theavy figure portrayal of deficit between the black heights of subtrees of node the gray color in illustrating and denotes the fact that these nodes may be colored either black or red