Editing Red–black tree (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.