Editing Red–black tree (section)

== Analogy to 2–3–4 trees ==
[[File:Red-black trees and 2–3–4 trees.svg|alt=A 2-node maps to a single black node. A 3-node maps to a black node with a red child. A 4-node maps to a black node with two red children.|thumb|Figure 1: Similarities between 2–3–4 trees and red-black trees]]

Red–black trees are similar in structure to [[2–3–4 trees]], which are [[B-trees]] of order 4.<ref>Using Knuth’s definition of order: the maximum number of children</ref> In 2–3–4 trees, each node can contain between 1 and 3 values and have between 2 and 4 children. These 2–3–4 nodes correspond to black node – red children groups in red-black trees, as shown in figure 1. It is not a [[1-to-1 correspondence]], because 3-nodes have two equivalent representations: the red child may lie either to the left or right. The [[left-leaning red-black tree]] variant makes this relationship exactly 1-to-1, by only allowing the left child representation. Since every 2–3–4 node has a corresponding black node, invariant 4 of red-black trees is equivalent to saying that the leaves of a 2–3–4 tree all lie at the same level.

Despite structural similarities, operations on red–black trees are more economical than B-trees. B-trees require management of vectors of variable length, whereas red-black trees are simply binary trees.<ref>{{Cite book |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) |url=https://archive.org/details/algorithmscparts00sedg |title=Algorithms in C++ |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-35088-3 |pages=[https://archive.org/details/algorithmscparts00sedg/page/n569 565]–575 |url-access=limited}}</ref>