Trying to implement a red-black tree in C

Question

I need help implementing a red-black tree It seems to keep seg faulting on my malloc calls. I am not sure how to fix it. Any advice would be greatly appreciated. The functions appear to be working the only issues i have are with allocating memory.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    char color;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

Node **Root = NULL;

// A utility function to create a new BST node
Node *newNode(int data) {
    Node *temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->color = 'R';
    temp->left = NULL;
    temp->right = NULL;
    temp->parent = NULL;

    return temp;
}

void rotateLeft(Node **Root, Node *New) {
    Node *lPtr = New->right;
    New->right = lPtr->left;

    if (lPtr->left != NULL)
        lPtr->left->parent = New;
    lPtr->parent = New->parent;
    if (New->parent == NULL)
        *Root = lPtr;
    else if (New->data == New->parent->left->data)
        New->parent->left = lPtr;
    else
        New->parent->right = lPtr;
    lPtr->left = New;
    New->parent = lPtr;
}

void rotateRight (Node**Root, Node *New) {
    Node *rPtr = New->left;
    New->left = rPtr->right;

    if (rPtr->right != NULL)
        rPtr->right->parent = New;
    rPtr->parent = New->parent;
    if (New->parent == NULL)
        *Root = rPtr;
    else if (New->data == New->parent->left->data)
        New->parent->left = rPtr;
    else
        New->parent->right = rPtr;
    rPtr->right = New;
    New->parent = rPtr;
}

void redBlackInsertFixup(Node **Root, Node *New) {
    Node* temp;
    while (New->parent->color == 'R') {
        if (New->parent->data == New->parent->parent->data) { 
            temp = New->parent->parent->right;
            if (temp->color == 'R') {
                New->parent->color = 'B';
                temp->color = 'B';
                New->parent->parent->color = 'R';
                New = New->parent->parent;
            } else
            if (New->data == New->parent->right->data) {
                New = New->parent;
                rotateLeft(Root,New);
            }
            New->parent->color = 'B';
            New->parent->parent->color = 'R';
            rotateRight(Root, New->parent->parent);
        } else {
            temp = New->parent->parent->left;
            if (temp->color == 'R') {
                New->parent->color = 'B';
                New->color = 'B';
                New->parent->parent->color = 'R';
                New = New->parent->parent;
            } else
            if (New->data == New->parent->left->data) {
                New = New->parent;
                rotateRight(Root, New);
            }
            New->parent->color = 'B';
            New->parent->parent->color = 'R';
            rotateLeft(Root, New->parent->parent);
        }
    }
    Root[0]->color = 'B';
}

void redBlackInsert(Node **Root, int data) {  
    Node *New = (Node *)malloc(sizeof(Node));
    New->data = data;
    New->left = NULL;
    New->right = NULL;
    New->color = 'R';
    Node *Yp = NULL;
    Node *Xp = *Root;
    if (*Root != NULL) {
        New->color = 'B';
        *Root = New;
        return;
    }
    while (Xp != NULL) {
        Yp = Xp;
        if (data < Xp->data)
            Xp = Xp->left;
        Xp = Xp->right;
    }
    New->parent = Yp;
    if (Yp == NULL) {
        *Root = New;
        if (data < Yp->data)
            Yp->left = New;
        else
            Yp->right = New;
    }
    New->left = NULL;
    New->right = NULL;
    New->color = 'R';
    redBlackInsertFixup(Root, New);
}

void redBlackTreePrint(Node *Root) {
    Node* temp = Root;
    if (temp != NULL) {
        redBlackTreePrint(temp->left);
        printf(" %d - %c,", temp->data, temp->color == 'B' ? 'B' : 'R');
        redBlackTreePrint(temp->right);
    }
    return;
}

int main(int argc, char *argv[]) {
    redBlackInsert(Root, 7);
    redBlackInsert(Root, 9);
    redBlackTreePrint(*Root);

    return 0;
}

Thanks!

Answer 1

Compile it with -g flags, and run with gdb, and you will find that it traps on line 120 at redBlackInsert because *Root is NULL.

scott > gcc -O0 -g redblack.c -o redblack
scott > redblack
Segmentation fault (core dumped)
scott > gdb redblack
(gdb) run
Starting program: /home/scott/stackOverflow/redblack/redblack 
Program received signal SIGSEGV, Segmentation fault.
0x000000000040098c in redBlackInsert (Root=0x0, data=7) at redblack.c:120
120     Node* Xp = *Root;
(gdb) bt
#0  0x000000000040098c in redBlackInsert (Root=0x0, data=7) at redblack.c:120
#1  0x0000000000400af5 in main (argc=1, argv=0x7fffffffded8) at redblack.c:164
(gdb) 

I modified the global Root to be "Node *Root" rather than "**Root" since this is more intuitive. Its three uses in main() had to be modified to match:

 int main(int argc, char* argv[])
 {
     redBlackInsert(&Root, 7);
     redBlackInsert(&Root, 9);
     redBlackTreePrint(Root);
     return 0;
 }

On 138, you check if yp==NULL, then you dereference it which causes a segmentation fault on 139:

(gdb) run
Starting program: /home/scott/stackOverflow/redblack/redblack 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a0f in redBlackInsert (Root=0x601050 <Root>, data=7) at redblack.c:139
139         if(data < Yp->data)
(gdb) bt
#0  0x0000000000400a0f in redBlackInsert (Root=0x601050 <Root>, data=7) at redblack.c:139
#1  0x0000000000400af2 in main (argc=1, argv=0x7fffffffded8) at redblack.c:165
(gdb) 

Sorry, that's as far as I got.