Кажется, определение в вики неточно:
http://en.wikipedia.org/wiki/Red-black_tree#Properties
Это дерево со всеми черными узлами - красно-черным деревом?
ОБНОВЛЕНИЕ
Если определение rbtree не столь строгое, как нам решить, печатать ли потомки черного узла как красные или как черные?