close nephew struct RBnode* D; // -> distant nephew // P != NULL, since N is not the root. dir = childDir(N); // side of parent P on which the node N is located // Replace N at its parent P by NIL: P->child[dir] = NIL; goto Start_D; // jump into the loop // start of the (do while)-loop: do { dir = childDir(N); // side of parent P on which node N is located Start_D: S = P->child[1-dir]; // sibling of N (has black height >= 1) D = S->child[1-dir]; // distant nephew C = S->child[ dir]; // close nephew if (S->color == RED) goto Case_D3; // S red ===> P+C+D black // S is black: if (D != NIL && D->color == RED) // not considered black goto Case_D6; // D red && S black if (C != NIL && C->color == RED) // not considered black goto Case_D5; // C red && S+D black // Here both nephews are == NIL (first iteration) or black (later). if (P->color == RED) goto Case_D4; // P red && C+S+D black The rebalancing loop of the delete operation has the following invariant: At the beginning of each iteration the black height of N equals the iteration number minus one, which means that in the first iteration it is zero and that N is a true black node in higher iterations. The number of black nodes on the paths through N is one less than before the deletion, whereas it is unchanged on all other paths, so that there is a black-violation at P if other paths exist. All other properties (including requirement 3) are satisfied throughout the tree. Notes to the delete diagrams In the diagrams below, P is used for N’s parent, S for the sibling of N, C (meaning close nephew) for S’s child in the same direction as N, and D (meaning distant nephew) for S’s other child (S cannot be a NIL node in the first iteration, because it must have black height one, which was the black height of N before its deletion, but C and D may be NIL nodes). The diagrams show the current node N as the left child of its parent P even though it is possible for N to be on either side. The code samples cover both possibilities by means of the side variable dir. At the beginning (in