Editing Red–black tree (section)

==== Notes to the insert diagrams ====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''before'' ||rowspan="2"|''case''||rowspan="2" {{verth|''rotation''}} ||rowspan="2" {{verth|''assign&shy;ment''}} ||colspan="4"| ''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x'' || '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x''
|-
| [[File:BlackNode.svg|13px]] || || || || [[#Insert case 1|'''I1''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || || [[#Insert case 2|'''I2''']] || || '''N''':='''G''' || {{dunno}} || || || || {{dunno}} || 2
|-
| — || || || || [[#Insert case 3|'''I3''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || — || || || [[#Insert case 4|'''I4''']] || || || [[File:BlackNode.svg|13px]] || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || i || [[#Insert case 5|'''I5''']] || '''P'''↶'''N''' || '''N''':='''P''' || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || '''I6''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || [[#Insert case 6|'''I6''']] || '''P'''↷'''G''' || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || || {{ya}} ||
|-
|colspan="13" style="text-align:left;font-size:smaller;"| 
;Insertion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases">The same partitioning is found in [[#Pfaff a|Ben Pfaff]].</ref> of constellations are covered.
|}
* In the diagrams, '''P''' is used for '''N'''’s parent, '''G''' for its grandparent, and '''U''' for its uncle. In the table, "—" indicates the root.
* 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 <code>dir</code>.
* 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 '''[[#Insert case 2|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''.
* A [[File:Check-green.svg|13px]] sign 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.
* In case '''[[#Insert case 2|2]]''' the problem of rebalancing is escalated <math>\Delta h=2</math> 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 <math>\tfrac{h}2</math> steps of iteration to repair the tree (where {{mvar|h}} 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|amortized constant]].
* Rotations occur in cases '''I6''' and '''I5 + I6''' – outside the loop. Therefore, at most two rotations occur in total.