3 ms·
My copy of Knuth is at home and I'm at work, so I can't check -- but does TAOCP actually cover red-black trees? My hazy memory says it doesn't, or if it does it
by gjm11 16y ago
My copy of Knuth is at home and I'm at work, so I can't check -- but does TAOCP actually cover red-black trees? My hazy memory says it doesn't, or if it does it gives them at most a passing mention.
(TAOCP is wonderful but I think the great majority of potential readers would be better served by Cormen/Leiserson/Rivest[/Stein]. But when you really need Knuth, nothing else will do.)
- michael_dorfman 16y agoAccording 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.