Hi, I'm trying to write a red black tree implementation that just holds an integer. I'm having trouble conceptualizing how to implement a sentinel NIL that will kind of keep me from trying to access things that aren't in my tree... I originally avoided this route, but have been told by classmates that it is the way to go. The problem I'm having is in setting it up so I don't have to pass it to every function. Here is what I've got right now for the sentinel part... it doesn't work though
Code:
main()
{
int flag=0, input;
struct node* root=NULL;
struct node* NIL;
NIL=malloc(sizeof(struct node));
NIL->parent=root;
NIL->left=NIL;
NIL->right=NIL;
NIL->data=0;
NIL->red=0;
printf("\n\n This program stores allows you to store"
"\n integers in or remove them from a red-black"
"\n binary search tree. Please use it responsibly.\n\n");
while(flag == 0)
{
rbtreemenu();
getinput(&input);
switch(input)
{
case 1:
root=addnode(root);
break;
case 2:
root=remnode(root);
break;
case -9:
flag=1;
break;
default:
printf("\n\n Please enter a valid option.\n");
break;
}
}
freenodes(root);
exit(0);
}
//-------------------------------------------------------------------------------
// This function adds a node to a binary search tree
struct node* addnode(struct node* root)
{
int input;
struct node* newnode, uncle;
struct node* NIL;
printf("\n\n Please enter an integer to add to the red-black tree.\n : ");
getinput(&input);
newnode=malloc(sizeof(struct node));
newnode->data=input;
newnode->red=1;
newnode->left=NULL;
newnode->right=NULL;
newnode->parent=NULL;
if(!root)
{ root=newnode;
root->red=0;
root->parent=NIL;
}
else
root=rbinsert(root, newnode);
//print the updated tree
printf("\n Your red-black tree in order is :");
printrbtree(root);
printf("\n The root node is %d,%c", root->data, root->red);
return root;
}
I was thinking I could just declare a new struct node pointer in each function and set it equal to root's parent, but I'm running into problems when root doesn't exist yet. Any ideas? I've had the stomach flu and have been living off of crackers and jello so maybe am not thinking all that clearly. Thanks.
oops, might help to know what's in my struct huh?
Code:
struct node
{
int data;
int red;
struct node* left;
struct node* right;
struct node* parent;
};
The idea behind the sentinel NIL as I understand it is to avoid/deal with situations where things in the tree move around and you end up referencing somehting that isn't there, like something above the root. Also, it gives a way to assign the color of the leaves to black.