Talk:Red–black tree#reqmovetag

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

The "Operations" section says that the examples are C++.

Are they. Looks like like plain C to me. Didn't want to change it, in case there is some C++ usage in there which I didn't spot.

It's certainly 90%+ C and a proper C++ implementation would look very different.

Good to change to "C" Oschonrock (talk) 16:33, 17 July 2024 (UTC)

:

:struct RBnode {

: RBnode* parent; // C would require 'struct RBnode* parent',

: RBnode* child[2]; // but C++ allows this kind of declaration

: enum color_t color;

: int key;

:};

:

:Technically no, but it could be changed easily. The style isn't consistent in the article. I suggest changing it all to the C++ style, or removing it entirely. (edited 10:40, 21 July 2024 (UTC)) IntGrah (talk) 17:07, 17 July 2024 (UTC)

The code in this article is not very well-written. In my opinion it should be pseudocode, since that's what most other CS articles seem to do. If not it should still be cleaned up a bit. Some glaring issues:

• Although the code is technically C++, it doesn’t really use any C++ features, the style is much more similar to C
• RBNode’s children being an array of length 2 with a bunch of associated macros is needlessly confusing. The children should be `left` and `right`. I understand the purpose of the array is to combine the left/right rotation functions into a single function, but why not just have two separate functions if it makes things clearer?
• The type `byte` is used arbitrarily in spots that don't make sense
• `The `goto` statements are confusing and it would be easier to just bunch all of the code together, and then have the sections afterwards explain each part. Or at least something that doesn't use `goto`.

The pseudocode in the Introduction To Algorithms textbook (linked below, start at page 331) is very concise but I'm unsure of how to carry it over without it being considered plagiarism.

[https://dl.ebooksworld.ir/books/Introduction.to.Algorithms.4th.Leiserson.Stein.Rivest.Cormen.MIT.Press.9780262046305.EBooksWorld.ir.pdf#page=353]https://dl.ebooksworld.ir/books/Introduction.to.Algorithms.4th.Leiserson.Stein.Rivest.Cormen.MIT.Press.9780262046305.EBooksWorld.ir.pdf#page=353 Begilbert238 (talk) 23:56, 20 July 2024 (UTC)

:I agree that the code is quite repugnant. GOTO considered harmful, inconsiderate use of macros, even the fact it is written in C …

:My proposal is to just straight up remove it. In my opinion, the pseudocode is useless in the current state of the article; most red–black tree implementations take several hundreds of lines of code, and spreading this across the article makes the operations seem a lot more complicated than they really are. The cryptic tables used in the explanation also have to go (The section Notes to the sample code and diagrams of insertion and removal > Notes to the insert diagrams).

:IntGrah (talk) 10:36, 21 July 2024 (UTC)

:I noticed this today and it triggered me so much I want through and cleaned up all the code. Also, it is all just C (not C++). It is much more readable now and is more organized. I didn't do too much to the rest of the article though. The majority of gotos are gone as well. Docter Vortex (talk) 02:25, 7 April 2025 (UTC)

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.

:{{ping|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)

::{{ping|Docter Vortex}} It seems an anonymous author also caught another issue and already fixed it in {{Diff2|1286110550|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)

The "Properties" and "Terminology" sections make reference to Figure 1 and Figure 2. However, these figures aren't actually on the page.

Where are the figures that are supposed to be used here? Eatmorepies (talk) 02:05, 17 April 2025 (UTC)

: {{re|Eatmorepies}} It perplexed me a bit, too. It turns out the Figures 1. and 2. have been here until the version Special:PermaLink/1284345512 from 7 April 2025, and then they have disappeared in the next edit Special:Diff/1284355892 one and half hour later. Both edits made by User:Docter Vortex. Apparently that was an action of deep code cleaning, mentioned above in the section #Re-writing the code. --CiaPan (talk) 12:43, 25 April 2025 (UTC)

::One of the figures had some inaccuracies with regards to what a leaf node is, so I removed it. The other figure got moved up closer to the start of the page, since it is mainly just an example of a RB tree. I can update the text to remove the erroneous references. Docter Vortex (talk) 19:39, 25 April 2025 (UTC)

::Okay, references to the changed/removed figures have been updated or removed. Docter Vortex (talk) 01:02, 27 April 2025 (UTC)

:::{{re|Docter Vortex}} OK, so now we have the 'example figure' term in the #Terminology section, which is hard to tell what figure it actually refers to, as well as two images described (and referred to) as 'Figure 3' and 'Figure 4', with lacking 'Figures' numbered 1. and 2. Are you sure the changes you made were an improvement to the article? Hopefully you could make the whole numbering consistent. {{smiley}} CiaPan (talk) 16:14, 27 April 2025 (UTC)

::::I'll update the numbers for figures 3 and 4 to 1 and 2. The example figure is File:Red-black_tree_example_with_sockets.svg, I'm not sure what else to call it. Docter Vortex (talk) 16:20, 27 April 2025 (UTC)