Editing Red–black tree (section)

=== Removal ===
==== Simple cases ====
* When the deleted node has '''2 children''' (non-NULL), then we can swap its value with its in-order successor (the leftmost child of the right subtree), and then delete the successor instead. Since the successor is leftmost, it can only have a right child (non-NULL) or no child at all.
* When the deleted node has '''only 1 child''' (non-NULL). In this case, just replace the node with its child, and color it black.
** The single child (non-NULL) must be red according to [[#con5|conclusion 5]], and the deleted node must be black according to [[#req3|requirement 3]].
* When the deleted node '''has no children''' (both NULL) and is the root, replace it with NULL. The tree is empty.
* When the deleted node '''has no children''' (both NULL), and '''is red''', simply remove the leaf node.
* When the deleted node '''has no children''' (both NULL), and '''is black''', deleting it will create an imbalance, and requires a rebalance, as covered in the next section.

==== Removal of a black non-root leaf ====
The complex case is when '''N''' is not the root, colored black and has no proper child (⇔ only NULL children).
In the first iteration, '''N''' is replaced by NULL.

<syntaxhighlight lang="c" line="1" linelinks="remove" copy>
void remove(struct Tree *tree, struct Node *node) {
	struct Node *parent = node->parent;

	struct Node *sibling;
	struct Node *close_nephew;
	struct Node *distant_nephew;

	enum Dir dir = DIRECTION(node);

	parent->child[dir] = NULL;
	goto start_balance;

	do {
		dir = DIRECTION(node);
start_balance:
		sibling = parent->child[1 - dir];
		distant_nephew = sibling->child[1 - dir];
		close_nephew = sibling->child[dir];
		if (sibling->color == RED) {
			// Case #3
			rotate_subtree(tree, parent, dir);
			parent->color = RED;
			sibling->color = BLACK;
			sibling = close_nephew;

			distant_nephew = sibling->child[1 - dir];
			if (distant_nephew && distant_nephew->color == RED)
				goto case_6;
			close_nephew = sibling->child[dir];
			if (close_nephew && close_nephew->color == RED)
				goto case_5;

			// Case #4
			sibling->color = RED;
			parent->color = BLACK;
			return;
		}

		if (distant_nephew && distant_nephew->color == RED)
			goto case_6;

		if (close_nephew && close_nephew->color == RED)
			goto case_5;

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

		// Case #1
		if (!parent) return;

		// Case #2
		sibling->color = RED;
		node = parent;

	} while (parent = node->parent);

case_5:

	rotate_subtree(tree, sibling, 1 - dir);
	sibling->color = RED;
	close_nephew->color = BLACK;
	distant_nephew = sibling;
	sibling = close_nephew;

case_6:

	rotate_subtree(tree, parent, dir);
	sibling->color = parent->color;
	parent->color = BLACK;
	distant_nephew->color = BLACK;
	return;
}</syntaxhighlight>

{{Anchor|loopInvariantD}}The rebalancing loop of the delete operation has the following [[Loop invariant|invariant]]:
* At the beginning of each iteration the black height of '''N''' equals the iteration number minus one, which means that in the first iteration it is zero and that '''N''' is a true black node [[File:BlackNode.svg|13px]] in higher iterations.
* The number of black nodes on the paths through '''N''' is one less than before the deletion, whereas it is unchanged on all other paths, so that there is a [[#ViolB|black-violation]] at '''P''' if other paths exist.
* All other properties (including [[#req3|requirement 3]]) are satisfied throughout the tree.

==== Notes to the delete 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|''assignment''}} ||colspan="4"|''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''C''' || '''S''' || '''D''' || '''P''' || '''C''' || '''S''' || '''D'''
|-
| — || || || || [[#Delete case 1|'''D1''']] || || || || || ||  ||  {{ya}}  ||
|-
| [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 2|'''D2''']] || || '''N''':='''P''' || {{dunno}} || || || || {{dunno}} || 1
|-
|rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:RedNode.svg]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[#Delete case D3|'''D3''']] ||rowspan="3"| '''P'''↶'''S''' ||rowspan="3"| '''N''':='''N''' || [[File:RedNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
|  [[File:RedNode.svg]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D5''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D4''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 4|'''D4''']] || || || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
| [[File:RedOrBlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 5|'''D5''']] || '''C'''↷'''S''' || '''N''':='''N''' || [[File:RedOrBlackNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
| [[File:RedOrBlackNode.svg|13px]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[#Delete case 6|'''D6''']] || '''P'''↶'''S''' || || [[File:BlackNode.svg|13px]] || || [[File:RedOrBlackNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
|colspan="13" style="text-align:left; font-size:smaller;"| 
;Deletion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases"/> of color constellations are covered.
|}
* In the diagrams below, '''P''' is used for '''N'''’s parent, '''S''' for the sibling of '''N''', '''C''' (meaning ''close'' nephew) for '''S'''’s child in the same direction as '''N''', and '''D''' (meaning ''distant'' nephew) for '''S'''’s other child ('''S''' cannot be a NULL node in the first iteration, because it must have black height one, which was the black height of '''N''' before its deletion, but '''C''' and '''D''' may be NULL nodes).
* The diagrams show the current node '''N''' as the left child of its parent '''P''' even though it is possible for '''N''' to be on either side. The code samples cover both possibilities by means of the side variable <code>dir</code>.
* At the beginning (in the first iteration) of removal, '''N''' is the NULL node replacing the node to be deleted. Because its location in parent’s node is the only thing of importance, it is symbolised by [[File:NilBlue.svg|8px]] (meaning: the current node '''N''' is a NULL node and left child) in the left column of the delete diagrams. As the operation proceeds also proper nodes (of black height &ge; 1) may become current (see e.g. case '''[[#Delete case 2|2]]''').
* By counting the black bullets ([[File:BlackNode.svg|13px]] and [[File:TriangleTop.svg]]) in a delete diagram it can be observed that the paths through '''N''' have one bullet less than the other paths. This means a black-violation at '''P'''—if it exists.
* The color constellation in column group ''before'' defines the case, whose name is given in the column ''case''. Thereby possible values in cells left empty are ignored.
* 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 iteration step. This possibly induces a reassignment of the other nodes '''P''', '''C''', '''S''', '''D''' 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.
* The loop is where the problem of rebalancing is escalated <math>\Delta h=1</math> level higher in the tree in that the parent '''P''' becomes the new current node '''N'''. So it takes maximally {{mvar|h}} iterations to repair the tree (where {{mvar|h}} is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed [[#amortized|amortized constant]]. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do ''not'' support constant amortized update costs."<ref name="Mehlhorn2008"/>{{rp|165,158}} This is true for the rebalancing after a deletion, but not AVL insertion.<ref>Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2</ref>)
* Out of the body of the loop there are exiting branches to the cases '''[[#Delete case 3|3]]''', '''[[#Delete case 6|6]]''', '''[[#Delete case 5|5]]''', '''[[#Delete case 4|4]]''', and '''[[#Delete case 1|1]]'''; section [[#Delete case 3|"Delete case 3"]] of its own has three different exiting branches to the cases '''6''', '''5''' and '''4'''.
* Rotations occur in cases '''6''' and '''5 + 6''' and '''3 + 5 + 6''' – all outside the loop. Therefore, at most three rotations occur in total.

==== Delete case 1 ====
The current node '''N''' is the new root. One black node has been removed from every path, so the RB-properties are preserved.
The black height of the tree decreases by 1.
==== Delete case 2 ====
<!--actions: eca-->
{{Multiple image
| align             = right
| state             = expanded
| header_align      = center
| header            = [[#explan|→ <small>Explanation of symbols</small>]]
| image1            = Red-black_tree_delete_case_B0t.svg
| width1            = 71
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_579_switch.svg
| width2            = 9
| image3            = Red-black_tree_delete_case_B1t.svg
| width3            = 117
| caption3          = <small>higher iteration</small>
| footer            = Delete case D2
}}

'''P''', '''S''', and '''S'''’s children are black. After painting '''S''' red all paths passing through '''S''', which are precisely those paths ''not'' passing through '''N''', have one less black node. Now all paths in the subtree rooted by '''P''' have the same number of black nodes, but one fewer than the paths that do not pass through '''P''', so [[#req4|requirement 4]] may still be violated. After relabeling '''P''' to '''N''' the [[#loopInvariantD|loop invariant]] is fulfilled so that the rebalancing can be iterated on one black level (= 1 tree level) higher.
==== Delete case 3 ====
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|image1=Red-black_tree_delete_case_A0rot3.svg
|width1=91
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_865_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_A1rot3.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D3
}}

The sibling '''S''' is red, so '''P''' and the nephews '''C''' and '''D''' have to be black. A {{nowrap|<code>dir</code>-rotation}} at '''P''' turns '''S''' into '''N'''’s grandparent.
Then after reversing the colors of '''P''' and '''S''', the path through '''N''' is still short one black node. But '''N''' now has a red parent '''P''' and after the reassignment a black sibling '''S''', so the transformations in cases 4, 5, or 6 are able to restore the RB-shape.
==== 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.

==== Delete case 5 ====
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|image1=Red-black_tree_delete_case_D0rot.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_919_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_D1rot.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D5
}}

The sibling '''S''' is black, '''S'''’s close child '''C''' is red, and '''S'''’s distant child '''D''' is black. After a {{nowrap|<code>(1-dir)</code>-rotation}} at '''S''' the nephew '''C''' becomes '''S'''’s parent and '''N'''’s new sibling. The colors of '''S''' and '''C''' are exchanged.
All paths still have the same number of black nodes, but now '''N''' has a black sibling whose distant child is red, so the constellation is fit for case D6. Neither '''N''' nor its parent '''P''' are affected by this transformation, and '''P''' may be red or black ([[File:RedOrBlackNode.svg]] in the diagram).
==== Delete case 6 ====
<!--actions: erc-->
{{Multiple image
|align=right
|state=expanded
|image1=Red-black_tree_delete_case_E0rot.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_639erc_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_E1rot.svg
|width3=96
|caption3=<small>higher iteration</small>
|footer=Delete case D6
}}

The sibling '''S''' is black, '''S'''’s distant child '''D''' is red. After a {{nowrap|<code>dir</code>-rotation}} at '''P''' the sibling '''S''' becomes the parent of '''P''' and '''S'''’s distant child '''D'''. The colors of '''P''' and '''S''' are exchanged, and '''D''' is made black. The whole subtree still has the same color at its root '''S''', namely either red or black ([[File:RedOrBlackNode.svg]] in the diagram), which refers to the same color both before and after the transformation. This way [[#req3|requirement 3]] is preserved. The paths in the subtree not passing through '''N''' (i.o.w. passing through '''D''' and node '''3''' in the diagram) pass through the same number of black nodes as before, but '''N''' now has one additional black ancestor: either '''P''' has become black, or it was black and '''S''' was added as a black grandparent. Thus, the paths passing through '''N''' pass through one additional black node, so that [[#req4|requirement 4]] is restored and the total tree is in RB-shape.

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