Editing Red–black tree (section)

== Implementation ==
The read-only operations, such as search or tree traversal, on a red–black tree require no modification from those used for [[binary search tree]]s, because every red–black tree is a special case of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red–black tree, the restoration of which is called ''rebalancing'' so that red–black trees become self-balancing.
{{anchor|amortized}}Rebalancing (i.e. color changes) has a worst-case time complexity of <math>O(\log n)</math> and average of <math>O(1)</math>,<ref name="tarjan">{{cite journal|last=Tarjan|first=Robert Endre|author-link=Robert Tarjan|title=Amortized Computational Complexity|journal=SIAM Journal on Algebraic and Discrete Methods|date=April 1985|volume=6|issue=2|pages=306–318|doi=10.1137/0606031|url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf}}</ref>{{rp|310}}<ref name="Mehlhorn2008"/>{{rp|158}} though these are very quick in practice. Additionally, rebalancing takes no more than three [[tree rotation]]s<ref>The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.</ref> (two for insertion).

This is an example implementation of insert and remove in [[C (programming language)|C]]. Below are the data structures and the <code>rotate_subtree</code> helper function used in the insert and remove examples.

<syntaxhighlight lang="c" line="1">enum Color { BLACK, RED };
enum Dir { LEFT, RIGHT };

// red-black tree node
struct Node {
	struct Node *parent; // null for the root node
	union {
		// Union so we can use ->left/->right or ->child[0]/->child[1]
		struct {
			struct Node *left;
			struct Node *right;
		};
		struct Node *child[2];
	};
	enum Color color;
	int key;
};

struct Tree {
	struct Node *root;
};

#define DIRECTION(N) (N == N->parent->right ? RIGHT : LEFT)

struct Node *rotate_subtree(struct Tree *tree, struct Node *sub, enum Dir dir) {

	struct Node *sub_parent = sub->parent;
	struct Node *new_root = sub->child[1 - dir]; // 1 - dir is the opposite direction
	struct Node *new_child = new_root->child[dir];

	sub->child[1 - dir] = new_child;

	if (new_child) new_child->parent = sub;

	new_root->child[dir] = sub;

	new_root->parent = sub_parent;
	sub->parent = new_root;
	if (sub_parent)
		sub_parent->child[sub == sub_parent->right] = new_root;
	else
		tree->root = new_root;

	return new_root;
}</syntaxhighlight>

[[File:Binary Tree Rotation (animated).gif|160px|thumb|right|Left rotation and<br/>right rotation, animated.]]{{Anchor|explan}}

=== Notes to the sample code and diagrams of insertion and removal ===
The proposal breaks down both insertion and removal (not mentioning some very simple cases) into six constellations of nodes, edges, and colors, which are called cases. The proposal contains, for both insertion and removal, exactly one case that advances one black level closer to the root and loops, the other five cases rebalance the tree of their own. The more complicated cases are pictured in a diagram.

* [[File:RedNode.svg|baseline]] symbolises a red node and [[File:BlackNode.svg|13px|baseline]] a (non-NULL) black node (of black height &ge; 1), [[File:RedOrBlackNode.svg|baseline]] symbolises the color red or black of a non-NULL node, but the same color throughout the same diagram. NULL nodes are not represented in the diagrams.
* The variable '''N''' denotes the current node, which is labeled <span style="background:black">&thinsp;<span style="color:white">N</span>&thinsp;</span> or <span style="background:red">&thinsp;<span style="color:white">N</span>&thinsp;</span> in the diagrams.
* A diagram contains three columns and two to four actions. The left column shows the first iteration, the right column the higher iterations, the middle column shows the segmentation of a case into its different actions.<ref name="pullout">The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also [[#C-eval|this remark]].)</ref>
# The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the [[#Properties|requirements]].<br/>A blue border rings the current node '''N''' and the other nodes are labeled according to their relation to '''N'''.
# If a [[tree rotation|rotation]] is considered useful, this is pictured in the next action, which is labeled "rotation".
# If some recoloring is considered useful, this is pictured in the next action, which is labeled "color".<ref>Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the [[Tail call|tail]].</ref>
# If there is still some need to repair, the cases make use of code of other cases and this after a reassignment of the current node '''N''', which then again carries a blue ring and relative to which other nodes may have to be reassigned also. This action is labeled "reassign".<br/>For both, insert and delete, there is (exactly) one case which iterates one black level closer to the root; then the reassigned constellation satisfies the respective loop invariant.
* A possibly numbered triangle with a black circle atop [[File:TriangleTop.svg|baseline]] represents a red–black subtree (connected to its parent according to [[#req3|requirement 3]]) with a black height equal to the iteration level minus one, i.e. zero in the first iteration. Its root may be red or black.<br/>A possibly numbered triangle [[File:TriangleSubtree.svg|baseline]] represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration.

{{anchor|C-eval}}
; Remark
: For simplicity, the sample code uses the [[Logical disjunction|disjunction]]:
:: <code>U == NULL || U->color == BLACK ''// considered black''</code>
: and the [[Logical conjunction|conjunction]]:
:: <code>U != NULL && U->color == RED &nbsp; ''// not considered black''</code>
: Thereby, it must be kept in mind that both statements are ''not'' evaluated in total, if <code>U == NULL</code>. Then in both cases <code>U->color</code> is not touched (see [[Short-circuit evaluation]]).<br/>(The comment <code>considered black</code> is in accordance with [[#consideredBlack|requirement 2]].)
: The related <code>if</code>-statements have to occur far less frequently if the proposal<ref name="pullout"/> is realised.

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

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