Editing Red–black tree (section)

==== Delete case 4 ====
<!--actions: ec-->
{{Multiple image
|align=right
|state=expanded
|image1=Red-black_tree_delete_case_C0.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_419_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_C1.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D4
}}

The sibling '''S''' and '''S'''’s children are black, but '''P''' is red. Exchanging the colors of '''S''' and '''P''' does not affect the number of black nodes on paths going through '''S''', but it does add one to the number of black nodes on paths going through '''N''', making up for the deleted black node on those paths.