Why inner child of a red node can't be null in the red black tree delete case when the sibling of the deleted black node is a red?

1
votes

I was reading the red black tree tutorial from Eternally confuzzled.

In the part where author explains the deletion of the nodes from a RB tree, authors asks readers to find the explanation as exercise:

It's obvious after seeing a diagram how this restores balance by fixing the black heights, but it's confusing why 2 becomes red. Well, the red has to go somewhere or the black height of the tree would be affected, and the only known node that we are sure can be made red is that particular child. I don't quite remember how I figured out the red sibling cases, but I'm reasonably sure that alcohol was involved. :-) The second red sibling case looks at the inner child of the sibling. This child cannot be a null pointer (exercise: why?), so we simply test one of its children and act depending on which one is red. If the outer child is red, we perform a double rotation, color the new parent black, its right child black, and its left child red:

How did the author conclude that the inner child of the sibling cannot be a null pointer? Why that particular child cannot be null pointer ? Why not the other child ?

2
data-structuresbinary-search-treered-black-tree

2 Answers

2
votes

If it were null, the tree wouldn't be valid, as this property wouldn't be satisfied:

Every red node must have two black child nodes.

Why is this property important?

If we ignore this property, we could get a valid red-black tree looking like this:

B
 \
  R
   \
    B
     \
      R
       \
        B
         \
         ...

This is of course the absolute worse-case for a binary search tree. It essentially makes it a linked-list - any operation would take O(n).

0
votes

I too have this same doubt which @Tipps raised. My understanding is that the author doesn't mention the property "Every red node must have two black child nodes" in the write-up. The article infers the properties a RB-Tree must hold given that it was born out of a B-Tree.

Maybe the case itself doesn't exist ? and I used free simulators on the web to verify that such a single-black-child-red-parent case shouldn't ideally exist in a valid RB-Tree

"Those are only the cases where the sibling is black. If the sibling is red, it's even worse. But I have good news for you too. The following discussion doesn't matter except as an intellectual curiosity." - from the same article

If you observe the RB-Tree re-balancing code which takes out the red-sibling case, you would see that there is no special case handling. Though I still wonder why :

if ( new_root )
  root = p;
else
   root->link[dir] = p;

is necessary ? wouldn't the single rotation have taken care of this update already ?