Editing Red–black tree (section)

=== Insertion ===
Insertion begins by placing the new (non-NULL) node, say '''N''', at the position in the [[binary search tree]] of a NULL node whose [[in-order traversal|in-order predecessor’s]] key compares less than the new node’s key, which in turn compares less than the key of its in-order successor.
(Frequently, this positioning is the result of a search within the tree immediately preceding the insert operation and consists of a node <code>P</code> together with a direction <code>dir</code> with {{nowrap|1=<code>P->child[dir] == NULL</code>.)}}
The newly inserted node is temporarily colored red so that all paths contain the same number of black nodes as before.
But if its parent, say '''P''', is also red then this action introduces a [[#ViolR|red-violation]].

<syntaxhighlight lang="c" line="1" linelinks="insert" copy>
// parent is optional
void insert(struct Tree *tree, struct Node *node, struct Node *parent, enum Dir dir) {
	
	
	node->color = RED;
	node->parent = parent;


	if (!parent) {
		tree->root = node;
		return;
	}

	parent->child[dir] = node;

	// rebalance the tree 
	do {
		// Case #1
		if (parent->color == BLACK) return;

		struct Node *grandparent = parent->parent;

		if (!grandparent) {
			// Case #4
			parent->color = BLACK;
			return;
		}

		dir = DIRECTION(parent);
		struct Node *uncle = grandparent->child[1 - dir];
		if (!uncle || uncle->color == BLACK) {
			if (node == parent->child[1 - dir]) {
				// Case #5
				rotate_subtree(tree, parent, dir);
				node = parent;
				parent = grandparent->child[dir];
			}

			// Case #6
			rotate_subtree(tree, grandparent, 1 - dir);
			parent->color = BLACK;
			grandparent->color = RED;
			return;
		}
	
		// Case #2
		parent->color = BLACK;
		uncle->color = BLACK;
		grandparent->color = RED;
		node = grandparent;

	} while (parent = node->parent);

	// Case #3
	return;

}
</syntaxhighlight>

{{Anchor|loopInvariantI}}The rebalancing loop of the insert operation has the following [[Loop invariant|invariants]]:
* '''Node''' is the current node, initially the insertion node.
* '''Node''' is red at the beginning of each iteration.
* [[#req3|Requirement 3]] is satisfied for all pairs node←parent with the possible exception '''node'''←'''parent''' when '''parent''' is also red (a [[#ViolR|red-violation]] at '''node''').
* All other properties (including [[#req4|requirement 4]]) are satisfied throughout the tree.

==== Notes to the insert diagrams ====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''before'' ||rowspan="2"|''case''||rowspan="2" {{verth|''rotation''}} ||rowspan="2" {{verth|''assign&shy;ment''}} ||colspan="4"| ''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x'' || '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x''
|-
| [[File:BlackNode.svg|13px]] || || || || [[#Insert case 1|'''I1''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || || [[#Insert case 2|'''I2''']] || || '''N''':='''G''' || {{dunno}} || || || || {{dunno}} || 2
|-
| — || || || || [[#Insert case 3|'''I3''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || — || || || [[#Insert case 4|'''I4''']] || || || [[File:BlackNode.svg|13px]] || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || i || [[#Insert case 5|'''I5''']] || '''P'''↶'''N''' || '''N''':='''P''' || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || '''I6''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || [[#Insert case 6|'''I6''']] || '''P'''↷'''G''' || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || || {{ya}} ||
|-
|colspan="13" style="text-align:left;font-size:smaller;"| 
;Insertion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases">The same partitioning is found in [[#Pfaff a|Ben Pfaff]].</ref> of constellations are covered.
|}
* In the diagrams, '''P''' is used for '''N'''’s parent, '''G''' for its grandparent, and '''U''' for its uncle. In the table, "—" indicates the root.
* The diagrams show the parent node '''P''' as the left child of its parent '''G''' even though it is possible for '''P''' to be on either side. The sample code covers both possibilities by means of the side variable <code>dir</code>.
* The diagrams show the cases where '''P''' is red also, the red-violation.
* The column ''x'' indicates the change in child direction, i.e. o (for "outer") means that '''P''' and '''N''' are both left or both right children, whereas i (for "inner") means that the child direction changes from '''P'''’s to '''N'''’s.
* The [[column group]] ''before'' defines the case, whose name is given in the column ''case''. Thereby possible values in cells left empty are ignored. So in case '''[[#Insert case 2|I2]]''' the sample code covers both possibilities of child directions of '''N''', although the corresponding diagram shows only one.
* The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible.
* The column ''rotation'' indicates whether a rotation contributes to the rebalancing.
* The column ''assignment'' shows an assignment of '''N''' before entering a subsequent step. This possibly induces a reassignment of the other nodes '''P''', '''G''', '''U''' also.
* If something has been changed by the case, this is shown in the column group ''after''.
* A [[File:Check-green.svg|13px]] sign in column ''next'' signifies that the rebalancing is complete with this step. If the column ''after'' determines exactly one case, this case is given as the subsequent one, otherwise there are question marks.
* In case '''[[#Insert case 2|2]]''' the problem of rebalancing is escalated <math>\Delta h=2</math> tree levels or 1 black level higher in the tree, in that the grandfather '''G''' becomes the new current node '''N'''. So it takes maximally <math>\tfrac{h}2</math> steps of iteration to repair the tree (where {{mvar|h}} is the height of the tree). Because the probability of escalation decreases exponentially with each step the total rebalancing cost is constant on average, indeed [[#amortized|amortized constant]].
* Rotations occur in cases '''I6''' and '''I5 + I6''' – outside the loop. Therefore, at most two rotations occur in total.

==== Insert case 1 ====
The current node’s parent '''P''' is black, so [[#req3|requirement 3]] holds. Requirement 4 holds also according to the [[#loopInvariantI|loop invariant]].
==== 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.
==== Insert case 3 ====
[[#Insert case 2|Insert case 2]] has been executed for <math>\tfrac{h-1}2</math> times and the total height of the tree has increased by 1, now being {{mvar|h}}&thinsp;.
The current node '''N''' is the (red) root of the tree, and all RB-properties are satisfied.
==== Insert case 4 ====
The parent '''P''' is red and the root.
Because '''N''' is also red, requirement 3 is violated. But after switching '''P'''’s color the tree is in RB-shape.
The black height of the tree increases by 1.
==== 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
}}

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