CODEWITHSUNDEEP
algorithmdata-structuresbinary-treered-black-tree
iSkull
iSkull

Reputation: 5

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!

Upvotes: 0

Views: 149

Answers (1)

trincot
trincot

Reputation: 351369

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*

Upvotes: 0

Related Questions