CODEWITHSUNDEEP
data-structurestreebinary-search-treered-black-tree
ansme
ansme

Reputation: 463

Why a Red Black Tree only rotated when the uncle of the inserted node is black? can someone explain the logic behind it's properties?

So lately I've been analyzing the Red black tree and it's properties and trying to reason behind why they are like that, I understand that these constraints are used to keep the tree balanced and efficient while maintaining it's height,but still I can't find a way to clearly understand that why we rotate the tree only when the uncle of the newly inserted node is black? and why we only recolor it when it's uncle is red? I'm trying to understand the logic behind all these properties can anyone please explain them? Any help is much appreciated!

Upvotes: 0

Views: 643

Answers (1)

SoronelHaetir
SoronelHaetir

Reputation: 15182

At least one rotation is needed during insertion when the uncle is black because there is a red-violation (two red nodes in a row) in this case but with the tree imbalanced no amount of re-coloring would fix it.

The simplest case

1b
 \
  2r
   \
    3r

1 and 2 each have a single leaf node (not shown), while 3 has two leaf nodes (also not shown). Ignoring node colors for a moment it is easy to see that a rotation is needed in order for this tree to balance, the recolorings that go along with that rotation are used to repair the red-black properties. When the second red node is out of alignment (right child of left child or left child of right child) a second rotation is needed because such a node is logically 'in between' its parent and grandparent.

With the tree:

   2b
  /  \
1r    3r
        \
         4r

The red node property is pushed up the tree because here no amount of rotation would fix the tree, any imbalance in the tree structure has to be at a level higher than what is shown here.

Upvotes: 1

Related Questions