3 ms·
Red-black trees have the same "black height" from the root to every leaf; red nodes do not count toward black height, but are limited in number: a red node cann
by kazinator 3y ago
Red-black trees have the same "black height" from the root to every leaf; red nodes do not count toward black height, but are limited in number: a red node cannot have red child. Thus at most half the nodes can be red in a given path to a leaf, and that keeps the tree sufficiently balanced for efficient search operations.
A 2-3 tree is formed from red-black when red nodes are absorbed into their parent as an extra child. We get a height-balanced tree (as required) since the equal black heights become actual heights.
When I learned that years ago, I lost interest in 2-3 trees.