Editing Red–black tree (section)

==== Notes to the delete 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|''assignment''}} ||colspan="4"|''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''C''' || '''S''' || '''D''' || '''P''' || '''C''' || '''S''' || '''D'''
|-
| — || || || || [[#Delete case 1|'''D1''']] || || || || || ||  ||  {{ya}}  ||
|-
| [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 2|'''D2''']] || || '''N''':='''P''' || {{dunno}} || || || || {{dunno}} || 1
|-
|rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:RedNode.svg]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[#Delete case D3|'''D3''']] ||rowspan="3"| '''P'''↶'''S''' ||rowspan="3"| '''N''':='''N''' || [[File:RedNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
|  [[File:RedNode.svg]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D5''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D4''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 4|'''D4''']] || || || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
| [[File:RedOrBlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 5|'''D5''']] || '''C'''↷'''S''' || '''N''':='''N''' || [[File:RedOrBlackNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
| [[File:RedOrBlackNode.svg|13px]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[#Delete case 6|'''D6''']] || '''P'''↶'''S''' || || [[File:BlackNode.svg|13px]] || || [[File:RedOrBlackNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
|colspan="13" style="text-align:left; font-size:smaller;"| 
;Deletion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases"/> of color constellations are covered.
|}
* In the diagrams below, '''P''' is used for '''N'''’s parent, '''S''' for the sibling of '''N''', '''C''' (meaning ''close'' nephew) for '''S'''’s child in the same direction as '''N''', and '''D''' (meaning ''distant'' nephew) for '''S'''’s other child ('''S''' cannot be a NULL node in the first iteration, because it must have black height one, which was the black height of '''N''' before its deletion, but '''C''' and '''D''' may be NULL nodes).
* The diagrams show the current node '''N''' as the left child of its parent '''P''' even though it is possible for '''N''' to be on either side. The code samples cover both possibilities by means of the side variable <code>dir</code>.
* At the beginning (in the first iteration) of removal, '''N''' is the NULL node replacing the node to be deleted. Because its location in parent’s node is the only thing of importance, it is symbolised by [[File:NilBlue.svg|8px]] (meaning: the current node '''N''' is a NULL node and left child) in the left column of the delete diagrams. As the operation proceeds also proper nodes (of black height &ge; 1) may become current (see e.g. case '''[[#Delete case 2|2]]''').
* By counting the black bullets ([[File:BlackNode.svg|13px]] and [[File:TriangleTop.svg]]) in a delete diagram it can be observed that the paths through '''N''' have one bullet less than the other paths. This means a black-violation at '''P'''—if it exists.
* The color constellation in column group ''before'' defines the case, whose name is given in the column ''case''. Thereby possible values in cells left empty are ignored.
* 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 iteration step. This possibly induces a reassignment of the other nodes '''P''', '''C''', '''S''', '''D''' 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.
* The loop is where the problem of rebalancing is escalated <math>\Delta h=1</math> level higher in the tree in that the parent '''P''' becomes the new current node '''N'''. So it takes maximally {{mvar|h}} iterations to repair the tree (where {{mvar|h}} is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed [[#amortized|amortized constant]]. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do ''not'' support constant amortized update costs."<ref name="Mehlhorn2008"/>{{rp|165,158}} This is true for the rebalancing after a deletion, but not AVL insertion.<ref>Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2</ref>)
* Out of the body of the loop there are exiting branches to the cases '''[[#Delete case 3|3]]''', '''[[#Delete case 6|6]]''', '''[[#Delete case 5|5]]''', '''[[#Delete case 4|4]]''', and '''[[#Delete case 1|1]]'''; section [[#Delete case 3|"Delete case 3"]] of its own has three different exiting branches to the cases '''6''', '''5''' and '''4'''.
* Rotations occur in cases '''6''' and '''5 + 6''' and '''3 + 5 + 6''' – all outside the loop. Therefore, at most three rotations occur in total.