@blowdart:
Actually that's not exactly correct. Red nodes must have black leaves, but black nodes can have black leaves too, so:
b
b b
r r r r
b b b b b b b b
is a valid tree.
Infact:
b
b b
b b b b
b b b b b b b b
would be a valid tree, except that it will never happen.
Also:
b
r b
b b r r
b b b b b b b b
is also valid.
The second tree will never happen because the rotation plus required color changes will guarantee the creation of a red node under certain circumstances in such a way that you will always have at least one red node.
That's the question. Also, I think I can explain the answer. But I want to think about it;)
