Editing Red–black tree (section)

==== Insert case 6 ====
<!--actions: erc-->The current node '''N''' is now certain to be an "outer" grandchild of '''G''' (left of left child or right of right child). Now {{nowrap|<code>(1-dir)</code>-rotate}} at '''G''', putting '''P''' in place of '''G''' and making '''P''' the parent of '''N''' and '''G'''. '''G''' is black and its former child '''P''' is red, since [[#req3|requirement 3]] was violated. After switching the colors of '''P''' and '''G''' the resulting tree satisfies requirement 3. [[#req4|Requirement 4]] also remains satisfied, since all paths that went through the black '''G''' now go through the black '''P'''.

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]].