D3 + D5 + D6 – all outside the loop. Therefore, at most three rotations occur in total. Delete case D1 The current node N is the new root. One black node has been removed from every path, so the RB-properties are preserved. The black height of the tree decreases by 1. // Case_D1 (P == NULL): return; // deletion complete Delete case D2 P, S, and S’s children are black. After painting S red all paths passing through S, which are precisely those paths not passing through N, have one less black node. Now all paths in the subtree rooted by P have the same number of black nodes, but one fewer than the paths that do not pass through P, so requirement 4 may still be violated. After relabeling P to N the loop invariant is fulfilled so that the rebalancing can be iterated on one black level (= 1 tree level) higher. // Case_D2 (P+C+S+D black): S->color = RED; N = P; // new current node (maybe the root) // iterate 1 black level // (= 1 tree level) higher } while ((P = N->parent) != NULL); // end of the (do while)-loop Delete case D3 The sibling S is red, so P and the nephews C and D have to be black. A at P turns S into N’s grandparent. Then after reversing the colors of P and S, the path through N is still short one black node. But N has a red parent P and a black sibling S, so the transformations in cases D4, D5, or D6 are able to restore the RB-shape. Case_D3: // S red && P+C+D black: RotateDirRoot(T,P,dir); // P may be the root P->color = RED; S->color = BLACK; S = C; // != NIL // now: P red && S black D = S->child[1-dir]; // distant nephew if (D != NIL && D->color == RED) goto Case_D6; // D red && S black C = S->child[ dir]; // close nephew if (C != NIL && C->color == RED) goto Case_D5; // C red && S+D black // Otherwise C+D considered black. // fall through to Case_D4 Delete case D4 The sibling S and S’s children are black, but P is red. Exchanging the colors of S and P does not affect the number of black nodes on paths going through S, but it does add one to the