Editing Red–black tree (section)

==== Delete case 6 ====
<!--actions: erc-->
{{Multiple image
|align=right
|state=expanded
|image1=Red-black_tree_delete_case_E0rot.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_639erc_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_E1rot.svg
|width3=96
|caption3=<small>higher iteration</small>
|footer=Delete case D6
}}

The sibling '''S''' is black, '''S'''’s distant child '''D''' is red. After a {{nowrap|<code>dir</code>-rotation}} at '''P''' the sibling '''S''' becomes the parent of '''P''' and '''S'''’s distant child '''D'''. The colors of '''P''' and '''S''' are exchanged, and '''D''' is made black. The whole subtree still has the same color at its root '''S''', namely either red or black ([[File:RedOrBlackNode.svg]] in the diagram), which refers to the same color both before and after the transformation. This way [[#req3|requirement 3]] is preserved. The paths in the subtree not passing through '''N''' (i.o.w. passing through '''D''' and node '''3''' in the diagram) pass through the same number of black nodes as before, but '''N''' now has one additional black ancestor: either '''P''' has become black, or it was black and '''S''' was added as a black grandparent. Thus, the paths passing through '''N''' pass through one additional black node, so that [[#req4|requirement 4]] is restored and the total tree is in RB-shape.

Because the algorithm transforms the input without using an auxiliary data structure and using only a small amount of extra storage space for auxiliary variables it is [[in-place algorithm|in-place]].