I understand that the black height of a RB tree increases when a red-red violation is propagated to the root, which then gets colored to red then recolored to black, and it causes for the black height of the tree to increase.
But I have been trying to come up with some examples that demonstarte the mentioned above, and the only scenario I can think of is of a perfect tree with alternating levels, starting with black root (of course) and ending with a red leaves level.
Are these kind of tree the only ones that experience the black height increase? If not, can you please give me other examples?
Thanks!