[SOLVED] Red Black Tree Black Height Increase after Insertion

Red Black Tree Black Height Increase after Insertion

I understand that the black height of a RB tree increases after insertion 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 after insertion? If not, can you please give me other examples?

Thanks!

Solution

the only scenario I can think of is of a perfect tree with alternating levels,

The tree doesn't have to be perfect. The path from the (black) root to the inserted (red) leaf must have these characteristics:

The nodes on that path have alternating colors, except for the inserted node and its parent which both are red.
Each red parent node in that path has a red sibling.

So the following tree is also an example where the insertion of R* will lead to an increase of the black-height, even though it is not a perfect tree:

          _______B______
         /              \
      __R__             _R_
     /     \           /   \
    B      _B_        B     B
   / \    /   \      / \   / \
  B   B  R     R    B   B B   B
        / \   / \
       B   B B   B
          / \
         R   R
          \
           R*

The red-violation will cascade up the tree and result in:

          _______B______
         /              \
      __B__             _B_
     /     \           /   \
    B      _R_        B     B
   / \    /   \      / \   / \
  B   B  B     B    B   B B   B
        / \   / \
       B   R B   B
          / \
         B   B
          \
           R*