4 ms·
According to the indices, Red-Black trees are mentioned once, on page 477 of Volume 3.
by michael_dorfman 16y ago
According to the indices, Red-Black trees are mentioned once, on page 477 of Volume 3.
- Locke1689 16y agoFair enough.
- gjm11 16y agoAnd here is the complete text of what Knuth says about red-black trees. "Elaboration of these ideas [2-3 trees, and a way of representing them as binary trees -- gjm] has led to many additional flavors of balanced trees, most notably the red-black trees, also called symmetric binary B-trees or half-balanced trees" ... followed by a list of references to places where these other sorts of tree, including red-black trees, are discussed. So, indeed, you wouldn't turn to Knuth for "red-black tree magic".
- Locke1689 16y agoOK, so change it to a "buddy-coalescing memory allocator." This is a pedantic conversation.