Talk:Red–black tree

Insertion, case 5 says:

"In this case, a right rotation on the parent P is performed; the result is a tree where the former parent P is now the parent of both the new node N and the former grandparent G."

It should say

"...a right rotation on the GRANDparent G is performed;..."

Most implementations define the rotation functions RotateRight(Node* n) or RotateLeft(Node* n) such that n is the root of the subtree being rotated, rather than one of the children. The code to implement the line in question would then be:

RotateRight(g);

rather than

RotateRight(p);

This could be just a terminology issue, but it will confuse people when they read source code and see irreconcilable differences with what is listed here.

It looks like the infobox lists the inventor of the antecedent to red-black trees rather than the inventor of red-black trees. — Preceding unsigned comment added by 45.49.18.32 (talk • contribs) 09:47, 23 January 2016

Mainly the sections #Terminology, #Properties, #Operations, #Proof of bounds have been revised.

• section #Properties
  • without rule 3: "root is black" (because this disturbs recursions)
  • then rules number 4 and 5 become 3 and 4
  • NIL leaves are never individuals, never "null leaves as actual node objects".

• section #Operations
• Both, Insertion and Deletion, now programmed iteratively. Advantages:
  • more precise visibility of the logic, the conditions of the cases
  • no need to observe tail-recursivity
  • rotations with root involvement easier
  • if-s with goto separate the iteration from solution which improves structure
  • (performance)
  • Both, Insertion and Deletion, cases slightly renumbered. Case 1 = iteration, Case 2 loop break, Insert Case 3 simple exit from loop.

Rotations are commutative with color changes, but consistently placed behind.

• diagrams:
  • 2 to 4 phases; from top to bottom
  • 2 or 3 if complete
  • 3rd or 4th if new assignment of current node for further processing
• section #Insertion:
  • new simple insert case 6
• section #Removal turned into 2 sections
  • simple cases (never loop)
  • case black leaf without child is more complex and possibly loops

• Finally, section #Proof of bounds
  • The section "Proof of asymptotic bounds" has been rewritten, mainly because the old version was introducing slightly deviating definitions of height and black height.
    The new version uses the definitions of #Properties.
  • It additionally gives an exact formula of the number of nodes of minimal RB trees.

• stylistic: fewer "Note that ..."
  • fewer "we"
  • fewer "in this case"
  • no "this test is trivial due to ..."

Why is this page at "red minus black" tree instead of "red hyphen black"? There's even a redirect there to this page. Why? — COArSe D1RTxxx (talk) 03:54, 8 January 2026 (UTC)Reply

The current implementation of case #2 in the removal reads like this:

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

	} while (parent = node->parent);

Note that this effectively reassigns node to previous grandparent, not the parent. I'm not certain, but this seems like a mistake in the implementation. The table of cases lists N:=P as the reassignment for D2, not N:=G. Starting the next iteration of the loop with N:=G doesn't satisfy the stated loop invariants. Specifically the invariant

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

doesn't hold anymore, because as stated in the description of case D2:

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 if the number of black nodes on the paths going through P is one lower than all other paths, then G can't have a consistent black height and thus can't satisfy the precondition above, because the precondition implies that all paths going through the new N go through the same number of black nodes.

Can anybody clarify if this is a mistake or if I'm just misunderstanding something? Kritzefitz (talk) 21:47, 7 November 2026 (UTC)Reply