I am having a problem with a segmentation fault in my program. Basically the program is a red black tree implementation. The seg fault happens at the same point in my code no matter what I insert and it's always after the third insertion, which causes a double red. I am using trinode restructuring to fix the double red.
Below is the code for insertion.
Code:
// Inserts a new key,element pair
void
RedBlackTree::insert( void * key, void * element)
{
RedBlackNode * parent=NULL;
RedBlackNode * curr=_root;
int result=0;
while (curr!=NULL){
parent=curr;
result=_compareFunc(curr->_key,key);
if (result==0){
curr->_element=element;
return;
}
else if (result>0){
curr=curr->_left;
}
else{
curr=curr->_right;
}
}//end while loop
RedBlackNode * n=new RedBlackNode(key,element,RED,NULL,NULL,_id,parent);
_id++;
if (parent==NULL){
_root=n;
return;
}
if (result>0){
parent->_left=n;
}else
{
parent->_right=n;
}
if (parent->_color==RED){
fixDoubleRed(n);
}
}
And here is the code that seg faults for the restructure
Code:
void
RedBlackTree::fixDoubleRed(RedBlackNode * node){
for (int d=0;d<32000;d++){for (int j=0;j<500;j++){}}
RedBlackNode * A;
RedBlackNode * B;
RedBlackNode * C;
RedBlackNode * x=node;
RedBlackNode * y=node->_parent;
RedBlackNode * z=node->_parent->_parent; // seg fault
printf("Finish Allocation of ABCxyz\n");
if (node->_parent->_parent->_right!=node->_parent){ //node's parent is $
if (node->_parent->_parent->_right->_color==BLACK)
The line that seg faults is the RedBlackNode *z=....
I am trying to input 1,then 7, then 4 as keys.
Anyone got any ideas why this line seg faults? Thanks