a reassignment of the current node N, which then again carries a blue ring and relative to which other nodes may have to be reassigned also. This action is labeled "reassign".For both, insert and delete, there is (exactly) one case which iterates one black level closer to the root; then the reassigned constellation satisfies the respective loop invariant. A possibly numbered triangle with a black circle atop represents a red–black subtree (connected to its parent according to requirement 3) with a black height equal to the iteration level minus one, i.e. zero in the first iteration. Its root may be red or black.A possibly numbered triangle represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration. Remark For simplicity, the sample code uses the disjunction: U == NIL || U->color == BLACK // considered black and the conjunction: U != NIL && U->color == RED // not considered black Thereby, it must be kept in mind that both statements are not evaluated in total, if U == NIL. Then in both cases U->color is not touched (see Short-circuit evaluation).(The comment considered black is in accordance with requirement 2.) The related if-statements have to occur far less frequently if the proposal is realised. Insertion Insertion begins by placing the new (non-NIL) node, say N, at the position in the binary search tree of a NIL node whose in-order predecessor’s key compares less than the new node’s key, which in turn compares less than the key of its in-order successor. (Frequently, this positioning is the result of a search within the tree immediately preceding the insert operation and consists of a node P together with a direction dir with The newly inserted node is temporarily colored red so that all paths contain the same number of black nodes as before. But if its parent, say P, is also red then this action introduces a red-violation. void RBinsert1( RBtree* T, // -> red–black tree struct RBnode* N, // -> node to be inserted struct RBnode* P, // -> parent node of N ( may be NULL ) byte dir) // side ( LEFT or RIGHT ) of P where to insert N { struct RBnode* G; // -> parent node of P struct RBnode* U; // -> uncle of N N->color = RED; N->left = NIL; N->right = NIL; N->parent = P;