Editing Red–black tree (section)

==== Insert case 2 ====
<!--actions: [e=entry,][r=rotation,][c=color,][a=reassign]-->
<!--actions: eca-->
{{Multiple image
| align             = right
| state             = expanded
| image1            = Red-black_tree_insert_case_B0t.svg
| width1            = 85
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_579_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_B1t.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 2
}}

If both the parent '''P''' and the uncle '''U''' are red, then both of them can be repainted black and the grandparent '''G''' becomes red for maintaining [[#req4|requirement 4]]. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent '''G''' may now violate requirement 3, if it has a red parent. After relabeling '''G''' to '''N''' the [[#loopInvariantI|loop invariant]] is fulfilled so that the rebalancing can be iterated on one black level (= 2 tree levels) higher.