Почему не перекрашиваются узлы в красно-черном дереве

Написал код для красно черного дерева, но заметил, что узлы не перекрашиваются, если это необходимо

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stddef.h>
    #include "rbtree.h"
    
    rbtree *null_node = &((rbtree){0, 0, 0, 0, 0, BLACK});
    
    rbtree* rbtree_add(rbtree *root, int key, char *value) {
      rbtree *node, *parent = null_node;
    
      while ((node != NULL) && (node != null_node)) {
        node = parent;
        if (key < node->key) 
          node = node->left;
        else if (key > node->key)
          node = node->right;
        else
          return root;
      }
      node = malloc(sizeof(*node));
      if (node == NULL) 
        return NULL;
      node->key = key;
      node->value = value;
      node->left = null_node;
      node->right = null_node;
      node->parent = parent;
      node->color = RED;
      if (parent != null_node) {
        if (key < parent->key)
          parent->left = node;
        else 
          parent->right = node;
      }
      else {
        root = node;
      }
      return fixup_add(root, node);
    }

rbtree* fixup_add(rbtree* root, rbtree* node) {
  rbtree* uncle;
  while(node != root && node->parent->color == RED) {
    if (node->parent == node->parent->parent->left) {
      uncle = node->parent->parent->right;
      // случай 1 дядя красный
      if (uncle->color == RED) {
        node->parent->color = BLACK;
        uncle->color = BLACK;
        node->parent->parent->color = RED;
        node = node->parent->parent;
      }
      // случай 2 дядя черный
      else {
        if(node == node->parent->right) {
          node = node->parent;
          rotate_left(node);
          root = node;
        }
        // случай 3 аналогично 2, дядя черный, но node является левым потомком
        node->parent->color = BLACK;
        node->parent->parent->color = RED;
        rotate_right(node->parent->parent);
        root = node;
      }
    }
     //случаи 4-6 симметричны, но node находится в правом поддереве дедушки
    else {
      uncle = node->parent->parent->right;
      if (uncle->color == RED) {
        node->parent->color = BLACK;
        uncle->color = BLACK;
        node->parent->parent->color = RED;
        node = node->parent->parent;
      }
      else {
        if (node == node->parent->left) {
          node = node->parent;
          rotate_right(node);
          root = node;
        }
        node->parent->color = BLACK;
        node->parent->parent->color = RED;
        rotate_left(node->parent->parent);
        root = node;
      }
    }
  }
  return root;
}

#include <stdio.h>
#include "rbtree.h"

int main(void) {
  rbtree* tree, *node, *search;
  tree = rbtree_add(node, 5, "Fox");
  printf("%d %s %d\n", tree->key, tree->value, tree->color);
  tree = rbtree_add(node, 8, "Cat");
  printf("%d %s %d\n", tree->key, tree->value, tree->color);
  tree = rbtree_add(node, 2, "Hey");
  printf("%d %s %d\n", tree->key, tree->value, tree->color);
}