Talk:Left-leaning red–black tree

Implementation notes

Details of how they work (including simple recursive implementation of insert):

Covered here by Sedgewick: https://class.coursera.org/algs4partI-002/lecture/50

— Preceding unsigned comment added by 82.34.15.102 (talk • contribs) 09:23, 10 March 2013

Not readable by non-experts

Both this article and the referenced paper by Sedgewick fail to state things in simple terms, presuming the reader to know the arbitrary numeric terminology of specific other sources by heart. Most notably, the concept of "Left-leaning" is not given a standalone definition such as (this may be wrong):

• A tree or subtree is left-leaning if all its nodes are left-leaning" (possibly wrong definition written just to represent a textual form of a stand-alone definition).
• A node is left-leaning if the maximum/average/whatever depth of its left subtree is greater than or equal / less than or equal than that of the right subtree" (possibly wrong definition written just to represent a textual form of a stand-alone definition).

From there, the explanation may be expanded by stating other similarly fundamental properties that some paper has proven from the definition combined with the 4 defining conditions of a Red-black tree. 2A01:4F0:4018:F0:FCBE:52CC:2157:85D0 (talk) 05:24, 29 June 2021 (UTC)

Properties of a left-leaning red–black tree

According to the paper quoted by Sedgewick (2008), the average tree height is about 2 ln N, not 2 lg N. Beowulf (talk) 01:29, 26 July 2022 (UTC)

That's right, I've gone ahead and fixed this. Noamz (talk) 06:45, 21 April 2024 (UTC)

Sedgewick's paper uses 'lg' and 'ln' interchangeably, and it's clear that he means the former. IntGrah (talk) 18:13, 26 April 2024 (UTC)

No, he does not use them interchangeably, rather he explicitly distinguishes between ln and lg on the first page of the paper. We don't have to guess his intentions because he shows the experimental results in the figure on page 8, with the graph of the expected tree height vs number of nodes N. For N = 50000 he indicates h = 21.7, which is very close to 2 ln 50000 = 21.639..., but far from 2 lg 50000 = 31.219... Noamz (talk) 18:20, 26 April 2024 (UTC)

I see now. Thanks for correcting me. On the first page, do you mean the exclamation mark he writes at "2 ln N (!)"? IntGrah (talk) 18:53, 26 April 2024 (UTC)

I'm not sure what he meant by the exclamation mark, but indeed I was referring to the fact that there are these two bullet points on the first page containing formulas in terms of lg and ln respectively. Noamz (talk) 12:59, 27 April 2024 (UTC)

Issue with the list of implementations

I have several issues with the table in the "Implementations" section:

1. Notability: I fail to see how these implementations are notable at all. Wikipedia is not a directory for listing algorithm implementations and, as such, we don't have lists of implementations in other articles about algorithms.
2. Quality: as of the current revision the table contains links to blogs, websites, personal GitHub repositories, even a YouTube video. How can we know that these implementations are correct or of good quality? The only one for which we have a reliable source is Sedgewick's original Java implementation.
3. Original research: the implication is that the table lists the first time an implementation, in a given programming language, was published on the internet. This is for sure original research, how can we be sure that these are really the first implementations of the algorithm? Again, the only one for which we have a reliable source is Sedgewick's.

To exemplify all the issues, the table currently references a YouTube video from 2021 as the Python implementation of LLRBTs, but, with a cursory Google search, I have found a Python implementation on GitHub from 2013. My impression is that the table is a random list of who decided that some implementation (perhaps their own implementation?) was the first and their name should be there. Therefore, I am removing the entire table. --CristianCantoro (talk) 10:06, 29 August 2023 (UTC)

Relationship with 2-3-4 trees

I tried to clarify the relationship between LLRBs and 2-3-4 trees in revision 07:33, 21 April 2024‎, following the description in Sedgewick's article. Previously, the article claimed incorrectly that LLRBs are isomorphic to 2-3 trees "in the same way conventional red-black trees are related to 2–3–4 trees". But now IntGrah has reverted my edit (as well as the other edit mentioned above about the issue of lg vs ln). I think that the confusion might be related to the previous version of the article 2–3–4 tree, where it was also claimed incorrectly that 2-3-4 trees are isomorphic to (ordinary) red-black trees. In any case, the relationship is very clear if you read the Sedgewick article. Let me quote a bit from p.2:

In [7], Guibas and Sedgewick showed that all of these algorithms can be implemented with red-black trees [....] In particular, the paper describes a way to maintain a correspondence between red-black trees and 2-3-4 trees, by interpreting red links as internal links in 3-nodes and 4-nodes. Since red links can lean either way in 3-nodes (and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1.

and on p.4 of the article: "The lean-to-the-left requirement gives a 1-1 correspondence between red-black and 2-3-4 trees and reduces the number of cases to consider". Noamz (talk) 18:47, 26 April 2024 (UTC)

on closer inspection, I think that the confusion might be due to this part of the current version of the Wikipedia article: "Additionally, the left-leaning property states that: 6. A node must not have a red right child." I don't think that is correct. Rather, as stated on p.1 of the Sedgewick article, the requirement is that "all 3-nodes lean left." In other words, if a black node has one red child and one black child, then its red child must be the left child (and the black child the right child). IntGrah, do you agree that this might have been the source of our disagreement? Sedgewick does explain how to modify the algorithms on LLRBs in order to maintain a correspondence with 2-3 trees in his article, but I think it is clear that by "left-leaning red-black trees" he is referring to the more general definition. Noamz (talk) 19:01, 26 April 2024 (UTC)

I see what you mean. The paper does talk about left-leaning red-black trees containing 4-nodes, as you said. But for most of the paper he talks about the 2-3 version. The implementations of each version differ in only a line of code. Should they be given equal weight? IntGrah (talk) IntGrah (talk) 19:30, 26 April 2024 (UTC)

I made an edit giving each version equal weight. IntGrah (talk) 20:12, 26 April 2024 (UTC)

Thanks, I think it's better now, although I'm not able to judge about how important is the LLRB concept overall and whether the 2-3 and 2-3-4 versions should be given equal weight. Instead of saying that "Left-leaning red-black trees can be made isomorphic to either 2–3 trees or 2–3–4 trees", I'd suggest to begin by describing the bijection between LLRBs and 2-3-4 trees, and then explain how it restricts to a bijection between LLRBs with no right red children and 2-3 trees. That's a very common situation in combinatorics: a bijection between two families of objects that restricts to a bijection between natural subfamilies. Noamz (talk) 12:55, 27 April 2024 (UTC)

I incorporated the suggestion and supported it with an image. IntGrah (talk) 14:02, 27 April 2024 (UTC)