c algorithm tree binary-search-tree red-black-tree

Red Black Tree Node Insertion Overwrites Previously Added Node

I have been working on an implementation of a RedBlack Tree that will be used as an internal data structure in a dynamic allocator written in C. I thought my insert_node and insert_fix functions were correct as used the pseudocode from the book Introduction to Algorithms: Third Edition, but I may be missing something in one of my functions, or the Tree structure itself.

Problem: Whenever I try to insert a new node into the tree, the previous node is overwritten and only the root remains as the valid node.

Code: The following is the code that handles insertions into a Tree struct (rb.h):

#include <inttypes.h>
#include <stdio.h>
#include <string.h>

typedef enum COLOR { BLACK, RED } COLOR;

typedef uintptr_t UPTR;
typedef uint64_t U64;

typedef struct TreeNode TreeNode;
struct TreeNode {
  TreeNode *parent;
  TreeNode *child[2];
  COLOR color;
  U64 blockSize;
  void *data;
};

typedef struct Tree Tree;
struct Tree {
  TreeNode *root;
  TreeNode *nil; // sentinel (implicitly BLACK)
};

#define NIL NULL
#define LEFT 0
#define RIGHT 1
#define left child[LEFT]
#define right child[RIGHT]

 void left_rotate(Tree *tree, TreeNode *node);
 void right_rotate(Tree *tree, TreeNode *node);
 void insert_fix(Tree *tree, TreeNode *node);
 void insert_node(Tree *tree, TreeNode *toInsert);
 void transplant(Tree *tree, TreeNode *n1, TreeNode *n2);
 void delete_fix(Tree *tree, TreeNode *node);
 void delete_node(Tree *tree, TreeNode *node);
 TreeNode *maximum(TreeNode *node);
 TreeNode *minimum(TreeNode *node);

 void left_rotate(Tree *tree, TreeNode *node) {
  if (tree != NIL && node != tree->nil) {
    TreeNode *rightChild = node->right;
    node->right = rightChild->left;

    if (rightChild->left != NIL) {
      rightChild->left->parent = node;
    }

    rightChild->parent = node->parent;

    if (node->parent == tree->nil) {
      tree->root = rightChild;
    } else if (node == node->parent->left) {
      node->parent->left = rightChild;
    } else {
      node->parent->right = rightChild;
    }

    rightChild->left = node;

    node->parent = rightChild;
  }
}

 void right_rotate(Tree *tree, TreeNode *node) {
  if (tree != NIL && node != tree->nil) {
    TreeNode *leftChild = node->left;
    node->left = leftChild->right;

    if (leftChild->right != NIL) {
      leftChild->right->parent = node;
    }

    leftChild->parent = node->parent;

    if (node->parent == tree->nil) {
      tree->root = leftChild;
    } else if (node == node->parent->right) {
      node->parent->right = leftChild;
    } else {
      node->parent->left = leftChild;
    }

    leftChild->right = node;

    node->parent = leftChild;
  }
}

 void insert_fix(Tree *tree, TreeNode *z) {
  // iterate until z is not the root and z's parent color is red
  while (z != tree->root && z->parent->color == RED) {
    if (z->parent == z->parent->parent->left) {
      TreeNode *y = z->parent->parent->right;
      if (y->color == RED) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else {
        if (z == z->parent->right) {
          z = z->parent;
          left_rotate(tree, z);
        }
        z->parent->color = BLACK;
        z->parent->color = RED;
        right_rotate(tree, z->parent->parent);
      }
    } else if (z->parent == z->parent->parent->right) {
      TreeNode *y = z->parent->parent->left;
      if (y->color == RED) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else {
        if (z == z->parent->left) {
          z = z->parent;
          right_rotate(tree, z);
        }
        z->parent->color = BLACK;
        z->parent->color = RED;
        left_rotate(tree, z->parent->parent);
      }
    } else {
      break;
    }
  }
  tree->root->color = BLACK; // keep root always black
}

 void insert_node(Tree *tree, TreeNode *z) {
  if (tree != NIL) {
    TreeNode *y = tree->nil;
    TreeNode *x = tree->root;

    while (x != NIL) {
      y = x;

      if (z->blockSize < x->blockSize) {
        x = x->left;
      } else {
        x = x->right;
      }
    }

    z->parent = y;

    if (y == tree->nil) {
      tree->root = z;
    } else if (z->blockSize < y->blockSize) {
      y->left = z;
    } else {
      y->right = z;
    }

    z->left = tree->nil;
    z->right = tree->nil;
    z->color = RED;
    insert_fix(tree, z);
  }
}

The following is my main function where I attempt to add 4 nodes to the tree and print the values stored in the tree:

#include "rb.h"

void print_inorder(Tree *t, TreeNode *n) {
  if (n != t->nil) {
    print_inorder(t, n->left);
    printf("%llu ", n->blockSize);
    print_inorder(t, n->right);
  }
}

int main(void) {
  printf("Hello World\n");
  Tree tree = {0};
  TreeNode nil = {0};

  nil.parent = NIL;
  nil.left = NIL;
  nil.right = NIL;
  nil.color = BLACK;
  nil.blockSize = 0;

  TreeNode n1 = {0};
  TreeNode n2 = {0};
  TreeNode n3 = {0};
  TreeNode n4 = {0};
  n1.parent = NIL;
  n1.left = NIL;
  n1.right = NIL;
  n1.color = BLACK;
  n1.blockSize = 48;

  n2.parent = NIL;
  n2.left = NIL;
  n2.right = NIL;
  n2.color = BLACK;
  n2.blockSize = 64;

  n3.parent = NIL;
  n3.left = NIL;
  n3.right = NIL;
  n3.color = BLACK;
  n3.blockSize = 128;

  n4.parent = NIL;
  n4.left = NIL;
  n4.right = NIL;
  n4.color = BLACK;
  n4.blockSize = 256;

  tree.nil = &nil;

  insert_node(&tree, &n1);
  insert_node(&tree, &n3);
  insert_node(&tree, &n4);
  insert_node(&tree, &n2);

  Tree *ptr = &tree;
  print_inorder(ptr, ptr->root);
  return 0;
}

The following is the output of the program when compiled and run (using a C repl):

make -s
./main
Hello World
64

After an hour or so of debugging, I believe there is something incorrect in this code block

  if (y == tree->nil) {
      tree->root = z;
    } else if (z->blockSize < y->blockSize) {
      y->left = z;
    } else {
      y->right = z;
    }

or the issue may be in the insert_fix function. Am I on the right track? Or am I missing something simple completely?

Any help would be appreciated!

So far I have tried several different implementations of the insert_fix and insert_node functions, but have not had much luck since I haven't gotten any consistent results. The above implementations are the closest I believe I have come to having a correct RedBlack Tree implementaion.

Solution

The problem is in this loop:

    while (x != NIL) {
      y = x;

      if (z->blockSize < x->blockSize) {
        x = x->left;
      } else {
        x = x->right;
      }
    }

Once you have a node in the tree, that node will have left/right pointers to tree->nil, and so the second time a node needs to be inserted, the loop will continue to visit those nil nodes and only stop when x is NULL. But that means y will be equal to tree->nil even when the tree was not empty; the loop should have made one iteration less.

In my opinion this just illustrates that it is a bad idea to work with tree->nil instead of just plain NULL. I can understand that using a real node instance for nil (that is black) can have some advantages while manipulating the tree, but the disadvantages are just as great, if not greater, as you have now seen here.

If you really want to continue using tree->nil, then the fix is to initialise tree (in your main function) with:

tree.nil = tree.root = &nil;

...and change the above loop condition to:

while (x != tree->nil) {

But if I were to implement this, I would use NULL instead of this tree->nil.