RB-properties are satisfied. // Leaving the (do while)-loop (after having fallen through from Case_I2). // Case_I3: N is the root and red. return; // insertion complete Insert case I4 The parent P is red and the root. Because N is also red, requirement 3 is violated. But after switching P’s color the tree is in RB-shape. The black height of the tree increases by 1. Case_I4: // P is the root and red: P->color = BLACK; return; // insertion complete Insert case I5 The parent P is red but the uncle U is black. The ultimate goal is to rotate the parent node P to the grandparent position, but this will not work if N is an "inner" grandchild of G (i.e., if N is the left child of the right child of G or the right child of the left child of G). A at P switches the roles of the current node N and its parent P. The rotation adds paths through N (those in the subtree labeled 2, see diagram) and removes paths through P (those in the subtree labeled 4). But both P and N are red, so requirement 4 is preserved. Requirement 3 is restored in case 6. Case_I56: // P red && U black: if (N == P->child[1-dir]) { // Case_I5 (P red && U black && N inner grandchild of G): RotateDir(P,dir); // P is never the root N = P; // new current node P = G->child[dir]; // new parent of N // fall through to Case_I6 } Insert case I6 The current node N is now certain to be an "outer" grandchild of G (left of left child or right of right child). Now at G, putting P in place of G and making P the parent of N and G. G is black and its former child P is red, since requirement 3 was violated. After switching the colors of P and G the resulting tree satisfies requirement 3. Requirement 4 also remains satisfied, since all paths that went through the black G now go through the black P. // Case_I6 (P red && U black && N outer grandchild of G): RotateDirRoot(T,G,1-dir); // G may be the root P->color = BLACK; G->color = RED; return; // insertion complete } // end of RBinsert1 Because the algorithm transforms the input without using an auxiliary data structure and using only a