-
Seg Fault Problem
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
-
A segmentation fault is when you dereference a bad pointer, whether it be NULL or some random location in memory that you don't own. The debugger is your friend, step through the code and find out why that line is accessing memory it doesn't own, then fix it.
-Prelude
-
C++ code moved to the C++ board
> RedBlackNode * z=node->_parent->_parent;
But if node is already the root of the tree, where does this take you?