if (P == NULL) { // There is no parent T->root = N; // N is the new root of the tree T. return; // insertion complete } P->child[dir] = N; // insert N as dir-child of P // start of the (do while)-loop: do { The rebalancing loop of the insert operation has the following invariant: The current node N is (red) at the beginning of each iteration. Requirement 3 is satisfied for all pairs node←parent with the possible exception N←P when P is also red (a red-violation at N). All other properties (including requirement 4) are satisfied throughout the tree. Notes to the insert diagrams In the diagrams, P is used for N’s parent, G for the grandparent, and U will denote N’s uncle. The diagrams show the parent node P as the left child of its parent G even though it is possible for P to be on either side. The sample code covers both possibilities by means of the side variable dir. N is the insertion node, but as the operation proceeds also other nodes may become current (see case I2). The diagrams show the cases where P is red also, the red-violation. The column x indicates the change in child direction, i.e. o (for "outer") means that P and N are both left or both right children, whereas i (for "inner") means that the child direction changes from P’s to N’s. The column group before defines the case, whose name is given in the column case. Thereby possible values in cells left empty are ignored. So in case I2 the sample code covers both possibilities of child directions of N, although the corresponding diagram shows only one. The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible. The column rotation indicates whether a rotation contributes to the rebalancing. The column assignment shows an assignment of N before entering a subsequent step. This possibly induces a reassignment of the other nodes P, G, U also. If something has been changed by the case, this is shown in the column group after. An arrow → in column next signifies that the rebalancing is complete with this step. If the column after determines exactly one case, this case is given as the subsequent one, otherwise there are question marks. The loop is contained in the sections "Insert case I1"