Editing Red–black tree (section)

=== Notes to the sample code and diagrams of insertion and removal ===
The proposal breaks down both insertion and removal (not mentioning some very simple cases) into six constellations of nodes, edges, and colors, which are called cases. The proposal contains, for both insertion and removal, exactly one case that advances one black level closer to the root and loops, the other five cases rebalance the tree of their own. The more complicated cases are pictured in a diagram.

* [[File:RedNode.svg|baseline]] symbolises a red node and [[File:BlackNode.svg|13px|baseline]] a (non-NULL) black node (of black height &ge; 1), [[File:RedOrBlackNode.svg|baseline]] symbolises the color red or black of a non-NULL node, but the same color throughout the same diagram. NULL nodes are not represented in the diagrams.
* The variable '''N''' denotes the current node, which is labeled <span style="background:black">&thinsp;<span style="color:white">N</span>&thinsp;</span> or <span style="background:red">&thinsp;<span style="color:white">N</span>&thinsp;</span> in the diagrams.
* A diagram contains three columns and two to four actions. The left column shows the first iteration, the right column the higher iterations, the middle column shows the segmentation of a case into its different actions.<ref name="pullout">The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also [[#C-eval|this remark]].)</ref>
# The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the [[#Properties|requirements]].<br/>A blue border rings the current node '''N''' and the other nodes are labeled according to their relation to '''N'''.
# If a [[tree rotation|rotation]] is considered useful, this is pictured in the next action, which is labeled "rotation".
# If some recoloring is considered useful, this is pictured in the next action, which is labeled "color".<ref>Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the [[Tail call|tail]].</ref>
# If there is still some need to repair, the cases make use of code of other cases and this after 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".<br/>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 [[File:TriangleTop.svg|baseline]] represents a red–black subtree (connected to its parent according to [[#req3|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.<br/>A possibly numbered triangle [[File:TriangleSubtree.svg|baseline]] represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration.

{{anchor|C-eval}}
; Remark
: For simplicity, the sample code uses the [[Logical disjunction|disjunction]]:
:: <code>U == NULL || U->color == BLACK ''// considered black''</code>
: and the [[Logical conjunction|conjunction]]:
:: <code>U != NULL && U->color == RED &nbsp; ''// not considered black''</code>
: Thereby, it must be kept in mind that both statements are ''not'' evaluated in total, if <code>U == NULL</code>. Then in both cases <code>U->color</code> is not touched (see [[Short-circuit evaluation]]).<br/>(The comment <code>considered black</code> is in accordance with [[#consideredBlack|requirement 2]].)
: The related <code>if</code>-statements have to occur far less frequently if the proposal<ref name="pullout"/> is realised.