Talk:Red–black tree

Possible insert case 5 error

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.

Why is Sedgewick not listed as the inventor?

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

Changes as of 2 Mar 2021

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

Incorrect removal algorithm?

I am trying to understand how the removal algorithm proceeds in some cases. It seems that once the while loop ends, it falls through to case_5. Is this intentional? Perhaps there should be a return immediately after the loop?

I am not confident enough to make the edit myself but if someone could confirm this is correct. Tombob51 (talk) 08:57, 15 April 2025 (UTC)

Edit: it also seems the code for "Case #1" (if (!parent) return) can never be triggered.

@Docter Vortex: Could you double-check this? Tombob51 (talk) 09:04, 15 April 2025 (UTC)

Sure, once I get some free time. Docter Vortex (talk) 19:40, 25 April 2025 (UTC)

@Docter Vortex: It seems an anonymous author also caught another issue and already fixed it in this revision. Can you cite a source for the basis behind the current code, or is this based on your own original research? If it's the latter, I sincerely appreciate that it IS much cleaner and easier to follow than the previous version of the article, but I worry that the code in its current state has not been thoroughly vetted for correctness, and doesn't cite any published work (peer-reviewed or otherwise) that can be used as a source of truth? Tombob51 (talk) 00:50, 27 April 2025 (UTC)

The current code is the same code as before, just combined into 2 blocks of coherent code. The control flow of previous code also was very difficult to understand, though I tried to put it "back together" as best as a I could. If you are concerned over whether the code is correct, please look into the work done by the original author. While I have almost a decade of programming experience, I primarily just did formatting here. Docter Vortex (talk) 00:56, 27 April 2025 (UTC)

Hi there, first-time poster, tagging in to say there is definitely a fatal error in the code for remove as-written. Line 59 guarantees the loop will not exit until parent is null, which is soon after followed by lines 71-73 which all dereference parent. Dposluns (talk) 17:34, 15 July 2025 (UTC)

"Red minus black"

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)