and "Insert case I2", where in case I2 the problem of rebalancing is escalated tree levels or 1 black level higher in the tree, in that the grandfather G becomes the new current node N. So it takes maximally steps of iteration to repair the tree (where is the height of the tree). Because the probability of escalation decreases exponentially with each step the total rebalancing cost is constant on average, indeed amortized constant. From the body of the loop, case I1 exits by itself and there are exiting branches to cases I4, I6, I5 + I6, and I3. Rotations occur in cases I6 and I5 + I6 – outside the loop. Therefore, at most two rotations occur in total. Insert case I1 The current node’s parent P is black, so requirement 3 holds. Requirement 4 holds also according to the loop invariant. if (P->color == BLACK) { // Case_I1 (P black): return; // insertion complete } // From now on P is red. if ((G = P->parent) == NULL) goto Case_I4; // P red and root // else: P red and G!=NULL. dir = childDir(P); // the side of parent G on which node P is located U = G->child[1-dir]; // uncle if (U == NIL || U->color == BLACK) // considered black goto Case_I56; // P red && U black Insert case I2 If both the parent P and the uncle U are red, then both of them can be repainted black and the grandparent G becomes red for maintaining requirement 4. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent G may now violate requirement 3, if it has a red parent. After relabeling G to N the loop invariant is fulfilled so that the rebalancing can be iterated on one black level (= 2 tree levels) higher. // Case_I2 (P+U red): P->color = BLACK; U->color = BLACK; G->color = RED; N = G; // new current node // iterate 1 black level higher // (= 2 tree levels) } while ((P = N->parent) != NULL); // end of the (do while)-loop Insert case I3 Insert case I2 has been executed for times and the total height of the tree has increased by 1, now being The current node N is the (red) root of the tree, and all