TAOCP is a reference book. Almost no one reads it cover-to-cover. It's the thing you pull out when you need to do some red-black tree magic that you've long since forgotten.
Personally, I still think K&R is the best CS/programming book I've ever read.
I'd disagree with that only because I (and everyone I've ever spoken to about it who has a CS degree) was forced to read it cover to cover (and for the record I hated it at first). The problem with saying it's a reference book is it isn't really written like a reference book. If you don't understand the context of what he's saying I don't see how it would be usable (especially considering the environment it describes is essentially hypothetical). So while I think it could be used as reference I think you have to have read it to use it in that fashion.
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.)
And 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".
Personally, I still think K&R is the best CS/programming book I've ever read.