Why do I have a red child from a red node in my Red Black Tree?

Question

in my Red Black Tree I have red child from red node, what was wrong in my code?

The struct for RBTree:

    num COLOR { RED, BLACK };
    
    // struct RBT
    typedef struct treeRBTnode {
      int key;
      enum COLOR color;
      struct treeRBTnode* parent;  // padre
      struct treeRBTnode* left;    // figlio sinistro
      struct treeRBTnode* right;   // figlio sinistro
    } RBTNode;
    
    typedef struct {
      int cardinality;
      struct treeRBTnode* root;
      struct treeRBTnode* Nil;
    } RBTree;

function to create a RBTree with T->Nil sentinel and create a new node:

    //Initialize RBT
    RBTree* InitializeRBT() {
      RBTree* T = (RBTree*)malloc(sizeof(RBTree));
      T->Nil = (RBTNode*)malloc(sizeof(RBTNode));
      T->cardinality = 0;
      T->Nil->left = T->Nil->right = T->Nil->parent = NULL;
      T->Nil->color = BLACK;
      T->Nil->key = 0;
      T->root = T->Nil;
      return T;
    }
 
//Create a new Node;
    //create a new node
    RBTNode* RBTnewNode(int key) {
      RBTNode* tmp = (RBTNode*)malloc(sizeof(RBTNode));
      tmp->key = key;
      tmp->color=RED;
      tmp->left = tmp->right = NULL;
      return tmp;

Now the insert algoritm with insertfixup, insertfixupleft and right, rotate left and right code:

void BSTreeRightRotate(RBTree* T, RBTNode* x) {
  RBTNode* y = x->left;
  x->left = y->right;
  if (y->right != T->Nil)
    y->right->parent = x;
  y->parent = x->parent;
  if (x->parent == T->Nil)
    T->root = y;
  if (x->parent != T->Nil && x == x->parent->left)
    x->parent->left = y;
  if (x->parent != T->Nil && x == x->parent->right)
    x->parent->right = y;
  y->right = x;
  x->parent = y;
}

//the same for leftRotate but with left and right reversed

void RBTreeInsertFixupRight(RBTree* T, RBTNode* x) {
  RBTNode* y = x->parent->parent->left;
  if (y->color == RED) {
    x->parent->color = BLACK;
    y->color = BLACK;
    x->parent->parent->color = RED;
    x = x->parent->parent;
  } else {
    if (x == x->parent->left) {
      x = x->parent;
      BSTreeRightRotate(T, x);
    }
    x->parent->color = BLACK;
    x->parent->parent->color = RED;
    BSTreeLeftRotate(T, x->parent->parent);
  }
}

//the same for fixupleft but with left and right reversed

void RBTreeInsertFixup(RBTree* T, RBTNode* x) {
  while (x->parent->color == RED) {
    if (x->parent == x->parent->parent->left) 
      RBTreeInsertFixupLeft(T, x);
    else
      RBTreeInsertFixupRight(T, x);
  }
  T->root->color = BLACK;
}

void RBTreeInsert(RBTree* T, RBTNode* x) {
  RBTNode* y = T->Nil;
  RBTNode* z = T->root;
  while (z != T->Nil) {
    y = z;
    if (x->key < z->key)
      z = z->left;
    else
      z = z->right;
  }
  x->parent = y;
  if (y == T->Nil)
    T->root = x;
  if (y != T->Nil && x->key < y->key)
    y->left = x;
  if (y != T->Nil && x->key >= y->key)
    y->right = x;
  x->left = T->Nil;
  x->right = T->Nil;
  x->color = RED;
  RBTreeInsertFixup(T, x);
}

Now after inserting elements in the tree through insert I realized that some red nodes sometimes have a red child, not respecting the validity of red blacks. I couldn't find the error in my code, could anyone help me?

Answer 1

This is wrong:

void RBTreeInsertFixupRight(RBTree* T, RBTNode* x) {
  RBTNode* y = x->parent->parent->left;
  if (y->color == RED) {

This assumes that y is a real node (the uncle) and it may not be. It may be NULL. If it NULL => the color is automatically BLACK. So the expression "y->color" may be dereferencing a NULL pointer.

The same issue applies to RBTreeInsertFixupLeft()