number of black nodes on paths going through N, making up for the deleted black node on those paths. Case_D4: // P red && S+C+D black: S->color = RED; P->color = BLACK; return; // deletion complete Delete case D5 The sibling S is black, S’s close child C is red, and S’s distant child D is black. After a at S the nephew C becomes S’s parent and N’s new sibling. The colors of S and C are exchanged. All paths still have the same number of black nodes, but now N has a black sibling whose distant child is red, so the constellation is fit for case D6. Neither N nor its parent P are affected by this transformation, and P may be red or black ( in the diagram). Case_D5: // C red && S+D black: RotateDir(S,1-dir); // S is never the root S->color = RED; C->color = BLACK; D = S; S = C; // now: D red && S black // fall through to Case_D6 Delete case D6 The sibling S is black, S’s distant child D is red. After a at P the sibling S becomes the parent of P and S’s distant child D. The colors of P and S are exchanged, and D is made black. The subtree still has the same color at its root, namely either red or black ( in the diagram), which refers to the same color both before and after the transformation. This way requirement 3 is preserved. The paths in the subtree not passing through N (i.o.w. passing through D and node 3 in the diagram) pass through the same number of black nodes as before, but N now has one additional black ancestor: either P has become black, or it was black and S was added as a black grandparent. Thus, the paths passing through N pass through one additional black node, so that requirement 4 is restored and the total tree is in RB-shape. Case_D6: // D red && S black: RotateDirRoot(T,P,dir); // P may be the root S->color = P->color; P->color = BLACK; D->color = BLACK; return; // deletion complete } // end of RBdelete2 Because the algorithm transforms the input without using an auxiliary data structure and using only a small amount of extra storage space for auxiliary variables it is in-place. Proof of bounds For there is a red–black tree of height