Editing Red–black tree (section)

==== Insert case 5 ====
<!--actions: era-->
{{Multiple image
| align             = left
| state             = expanded
| image1            = Red-black_tree_insert_case_C0.svg
| width1            = 64
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_639era_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_C1.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 5
}}

The parent '''P''' is red but the uncle '''U''' is black. The ultimate goal is to rotate the parent node '''P''' to the grandparent position, but this will not work if '''N''' is an "inner" grandchild of '''G''' (i.e., if '''N''' is the left child of the right child of '''G''' or the right child of the left child of '''G'''). A {{nowrap|<code>dir</code>-rotation}} at '''P''' switches the roles of the current node '''N''' and its parent '''P'''. The rotation adds paths through '''N''' (those in the subtree labeled '''2''', see diagram) and removes paths through '''P''' (those in the subtree labeled '''4'''). But both '''P''' and '''N''' are red, so [[#req4|requirement 4]] is preserved. Requirement 3 is restored in case 6.

{{Multiple image
| align             = right
| state             = expanded
| image1            = Red-black_tree_insert_case_D0rot.svg
| width1            = 64
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_639erc_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_D1rot.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 6
}}