Ensure every path from root to a tree leaf node has the same number of black nodes ( C )

Question

I'm implementing a Red-Black tree for universities purpose and I'm stuck on the property that each path from root to a leaf should have the same number of black nodes. I've inserted all the functions needed : fixup, rotation, insertion...But I don't know how to handle this function. I was thinking something like :

void checkNuberBlackNodes(struct node* root) {
    if( numberBlackNodes(root->right) > numberBlackNodes(root->left) {
         leftRotate(root);
         colorize(root);
    }
    else if( numberBlackNodes(root->right) < numberBlackNodes(root->left) {
         rightRotate(root);
         colorize(root);
    }
    else return; //no violation, same number of black nodes
}

The idea is to insert a node, fix up the violation and then checkNumberBlackNodes on the new node inserted (or from root). I don't know how handle this process, all the previous functions were pretty easy to implement this is...I don't know how I could start. Edit : I had a new idea :

void checkNuberBlackNodes(struct node* root) {
  int diff = height(root->right) - height(root->left);
  if ( diff >=2 ) //if the tree is too deep
  {
     leftRotate(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
  else if ( diff <= -2 ) //specular case
  { 
     rightRotate(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
  else if( blackHeight(root->right) > blackHeight(root->left) {
     colorize(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
else if( blackHeight(root->right) < blackHeight(root->left) {
     colorize(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
else return; //No violation
}

blackHeight is the number of black nodes in that path from node to leaf;

Answer 1

If you insert a new node into a Red-Black tree, the node is always a leaf node at the end. And invariably it is coloured Red.

Generally

(1) Inserting a Node may violate the "no consecutive Red nodes" rule and fixups will be in the direction of the root. A maximum of 2 rotations and 3 * O(h/2) recolourations are required where h is the height of the tree. If the parent of the inserted Node is black, no fixups are required.

(2) Deleting a Node may violate the "count of black nodes from root down every path is the same" rule. Again, fixups occur towards to root. A maximum of 3 rotations and O(h) recolourations are required where h is the height of the tree.

If the Node to be deleted is a the root node with no children, delete it.

If the Node to be deleted has a two children, find the immediate successor (right child then leftwards all the way), swap the Node and successor Node (but PRESERVE the original colours of nodes). The successor Node will always be a 0-children or 1-child node. Now you need to delete the original Node but in the position of the successor. You move to the next two cases.

If the Node deleted is a leaf node and is red, no fixups are required, delete the node

If the Node to be deleted has a single child, it is black, the child is red, delete the node, replace the Node with the child, recolour the child as black.

So what does this leave? It leaves a black node that is a leaf node, no children, the difficult case. Deleting this will violate the "count of black nodes from root down every path is the same" rule.

Having deleted the node, the parent node now has the black path count wrong down one side of the tree. Basically deletion is a two-prong strategy:

a) You examine the parent node, the sibling node, and sibling children's nodes to see if any are red. If they are you can using rotations and recolourations shift this, so the black hole on the deleted side is refilled, repairing tree. b) and if all the nodes (or NULL nodes) are black, then you make the sibling node red, and the parent node is now considered the point to repair the tree. You have made both sides of tree equally bad and now the fixup point is 1-level higher. You go back to step a) as there is new definition of "parent", "sibling" and "sibling children". c) It is possible to have a red-black tree which is entirely black. What happens if you reach the root and no red nodes are encountered? Then it now a red-black tree. Effectively , changing siblings has introduced 1 red node in every tree path, reducing the black tree height by 1 uniformly everywhere.