data-structurestreelanguage-agnosticred-black-tree

Red Black Trees - Since every leaf has two null children, why even bother calling those black?


I've been watching nothing but CS lectures about Red Black Trees and every single one, when counting the black height of the tree, counts the NULL Nodes as Black. Why even bother? For example, the following tree:

enter image description here

If I asked you, what is the black height of this tree, you would say three. But, if I shaved off all of the NULL Nodes (because they are implied) and asked you again, you would say two. Does it really make a difference? I know some algorithms like the Insertion case where you must check if the Uncle is Black but you would write that in code like the following:

Node *uncle = uncle(child);
if (uncle == NULL || uncle->color == BLACK)

You wouldn't write it as

if (uncle->color == BLACK)

So if it doesn't matter when looking at the tree, and in the code, we have to check for NULL separately from the color, why even call them the same thing to begin with?


Solution

  • The reason why you have to check if uncle is null while inserting is that although a leaf's children are considered black nodes, they are still null in essence. This leads to the reason you have to check if uncle == null before checking if uncle-> color == BLACK. If uncle is indeed a leaf's child aka null, then you know it's a leaf's child and cannot further proceed onto the other half of the conditional or else you will get an exception (trying to check the color of a null object will throw some exception). However, you still need that other half of the conditional to check for actual black objects in the tree.

    But I guess another part of your question is why make the children of leaves black in the first place?

    Consider this picture from http://www.geeksforgeeks.org/red-black-tree-set-2-insert/ enter image description here

    After inserting 30 to the tree above, 30's uncle now has to be checked since there are now two adjacent red nodes. Notice though that 10's left child aka 30's uncle is null. Since a null object indicates a black object, you know that rotation case 2 must occur. How would you check to do this in code? Look at the code in your question,

    if (uncle == NULL || uncle->color == BLACK)
    

    You can't just simply check uncle's color because there may be instances where the uncle is 'null', making it impossible to check the color. The color of a leaf's children are black in concept, hence the picture in your question. Otherwise, we wouldn't be calling the leaf's children null, we'd be calling them black objects.