I have a seg fault I can't seem to be rid of. Basically I'm building an AVL tree and I'm stuck on the insert method. gdb says it is occuring on the line with:

while( temp != NULL && temp->key != k ){

Would someone please help? Thank you in advance.

#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<fstream>
#include <stdlib.h> 

using namespace std;

struct AVLNode{
    public:
    int balance;
	int key;
	string data;
	AVLNode* leftchild;
	AVLNode* rightchild;


};

class AVLTree{

    public:
    AVLNode *root;
    
    /*
	*inserts a new node given the paramaters
    *in a the same fashion as a binary search tree
    *and then checks to see if AVL is violated
    * k is the key of the node which is an integer
    * d is the string for the info field
    * r is the root node of the AVL Tree
    */
    void AVLTreeInsert( int k, string d){
		
	 AVLNode *temp = this->root; 
        AVLNode *critNode;
        AVLNode *Rnode;
        bool critNodeFound = false;	 

	 cout << "what is up here" << endl;
        cout << temp->key << endl;
	 cout << "i don't know" << endl;
        while(  temp != NULL && temp->key != k ){
		
		    if( temp->balance != 0 ){
				critNode = temp;
				critNodeFound = true;
		    }
		    if( k < temp->key ){
				
			 	temp = temp->leftchild;
		    }
		    else
		        temp = temp->rightchild;
		}
		if(  temp != NULL ){
		
		    temp->data = d;
		    return;
		}
		
		temp->data = d;
		temp->key = k;
		temp->leftchild = NULL;
		temp->rightchild = NULL;
		temp->balance = 0;
		
		if( !critNodeFound ){
			
			Rnode = this->root;
		}
		else{
            int d1;
            int d2;
            int d3;
            AVLNode *Cnode;
            AVLNode *Bnode;
            
            if( k == critNode->key ){
                d1 = 0;
                Cnode = critNode;
			}
            else if( k < critNode->key ){
                d1 = -1;
                Cnode = critNode->leftchild;
			}
            else{
                d1 = 1;
                Cnode = critNode->rightchild;
			}	
					
			
            if( critNode->balance != d1 ){
			   critNode->balance = 0;
               Rnode = temp;
		    }
		    else{
	            if( k == Cnode->key ){
	                d2 = 0;
	                Bnode = Cnode;
				}
	            else if( k < Cnode->key ){
	                d2 = -1;
	                Bnode = Cnode->leftchild;
				}
	            else{
	                d2 = 1;
	                Bnode = Cnode->rightchild;
				}
				if( d2 == d1 ){
				    critNode->balance = 0;
				    Rnode = Bnode;
				    rotate(critNode, -d1);
				
				}
				else{
		            if( k == Bnode->key ){
		                d3 = 0;
		                Rnode = Bnode;
					}
		            else if( k < Bnode->key ){
		                d3 = -1;
		                Rnode = Bnode->leftchild;
					}
		            else{
		                d3 = 1;
		                Rnode = Bnode->rightchild;
					}
					
					if( d3 = d2){
					    critNode->balance = 0;
					    Cnode->balance = d1;	
					}
					else if( d3 = -d2){
					    critNode->balance = d2;	 
		            }
		            else{
				        critNode->balance = 0;
					}
					rotate(Cnode, -d2);
					rotate(critNode, -d1);
				}
				 
		    }
		
		}
		while( Rnode->key != k ){
            if( k == Rnode->key ){
                Rnode->balance = 0;
                Rnode = Rnode;
			}
            else if( k < Rnode->key ){
                Rnode->balance = -1;
                Rnode = Rnode->leftchild;
			}
            else{
                Rnode->balance = 1;
                Rnode = Rnode->rightchild;
			}	   
        }
		
		
		
		
    }// end insert function
    
    
	void rotate( AVLNode *rotateNode, int d ){
		 
		 AVLNode *temp = rotateNode;
		 if( d == -1 ){
		 	 rotateNode = rotateNode->rightchild;
		 	 temp->rightchild = temp->rightchild->leftchild;
		 	 temp->rightchild->leftchild = temp;
		 
		 }
		 else    
		 	 rotateNode = rotateNode->leftchild;
		 	 temp->leftchild = temp->leftchild->rightchild;
		 	 temp->leftchild->rightchild = temp;	
	}//end Rotate function

};

int main( int argc, char* argv[] ){

	AVLTree tree;
	vector<string> avlvector;
	string input;
	ifstream argfile( "input.txt" );
	if( argfile.is_open() ){
		while( !argfile.eof() ){

			getline( argfile, input );
			avlvector.push_back(input);
		}
		argfile.close();

	}

	string s;
	
	int i = 0;
	string helper;
	char* number;
	int num;
      while( i < avlvector.size() ){
     	 s = avlvector.at(i);
      	 helper = s.substr(0,2);
      	 number = new char[helper.size() + 1 ];
      	 strcpy( number, helper.c_str() );
      	 num = atoi(number);
	 tree.AVLTreeInsert( num, s.substr(3,5));
	 i++;	   
      }
    
	
	while(1){}


}

in class AVLTree:
You are not initializing root.
Add a constructor and initialize the root with NULL in there.

AVLTree()
{
    root = NULL;
}

sure, temp is NULL, but i don't see where you add a new node with "new AVLNode"?

good catch....

Thanks for the replies, still looking for the answer.

well, not to be NULL, you should add a AVLTree Object

Well I do have one, or am I missing something?

the only new which i see at line 211....

Ok, I thought you had to have a constructor to use new.

Updated code. Is this what you were talking about Doesn't work yet though.

#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<fstream>
#include <stdlib.h> 

using namespace std;

struct AVLNode{
    public:
    int balance;
	int key;
	string data;
	AVLNode* leftchild;
	AVLNode* rightchild;


};

class AVLTree{

    public:
    AVLNode *root;
    
    AVLTree(){
	    root = NULL;		  
    }
    
    /*
	*inserts a new node given the paramaters
    *in a the same fashion as a binary search tree
    *and then checks to see if AVL is violated
    * k is the key of the node which is an integer
    * d is the string for the info field
    * r is the root node of the AVL Tree
    */
    void AVLTreeInsert( int k, string d){
		
	    AVLNode *temp = new AVLNode;
		temp = this->root; 
        AVLNode *critNode = new AVLNode;
		critNode = 0;
        AVLNode *Rnode = new AVLNode;
		Rnode = 0;
        bool critNodeFound = false;
        
	 
        while(  temp != NULL && temp->key != k ){
		
		    if( temp->balance != 0 ){
				critNode = temp;
				critNodeFound = true;
		    }
		    if( k < temp->key ){
				
			 	temp = temp->leftchild;
		    }
		    else
		        temp = temp->rightchild;
		}
		if(  temp != NULL ){
		
		    temp->data = d;
		    return;
		}
		
		temp->data = d;
		temp->key = k;
		temp->leftchild = NULL;
		temp->rightchild = NULL;
		temp->balance = 0;
		
		if( !critNodeFound ){
			
			Rnode = this->root;
		}
		else{
            int d1;
            int d2;
            int d3;
            AVLNode *Cnode;
            AVLNode *Bnode;
            
            if( k == critNode->key ){
                d1 = 0;
                Cnode = critNode;
			}
            else if( k < critNode->key ){
                d1 = -1;
                Cnode = critNode->leftchild;
			}
            else{
                d1 = 1;
                Cnode = critNode->rightchild;
			}	
					
			
            if( critNode->balance != d1 ){
			   critNode->balance = 0;
               Rnode = temp;
		    }
		    else{
	            if( k == Cnode->key ){
	                d2 = 0;
	                Bnode = Cnode;
				}
	            else if( k < Cnode->key ){
	                d2 = -1;
	                Bnode = Cnode->leftchild;
				}
	            else{
	                d2 = 1;
	                Bnode = Cnode->rightchild;
				}
				if( d2 == d1 ){
				    critNode->balance = 0;
				    Rnode = Bnode;
				    rotate(critNode, -d1);
				
				}
				else{
		            if( k == Bnode->key ){
		                d3 = 0;
		                Rnode = Bnode;
					}
		            else if( k < Bnode->key ){
		                d3 = -1;
		                Rnode = Bnode->leftchild;
					}
		            else{
		                d3 = 1;
		                Rnode = Bnode->rightchild;
					}
					
					if( d3 = d2){
					    critNode->balance = 0;
					    Cnode->balance = d1;	
					}
					else if( d3 = -d2){
					    critNode->balance = d2;	 
		            }
		            else{
				        critNode->balance = 0;
					}
					rotate(Cnode, -d2);
					rotate(critNode, -d1);
				}
				 
		    }
		
		}
		while( Rnode->key != k ){
            if( k == Rnode->key ){
                Rnode->balance = 0;
                Rnode = Rnode;
			}
            else if( k < Rnode->key ){
                Rnode->balance = -1;
                Rnode = Rnode->leftchild;
			}
            else{
                Rnode->balance = 1;
                Rnode = Rnode->rightchild;
			}	   
        }
		
		
		
		
    }// end insert function
    
    
	void rotate( AVLNode *rotateNode, int d ){
		 
		 AVLNode *temp = rotateNode;
		 if( d == -1 ){
		 	 rotateNode = rotateNode->rightchild;
		 	 temp->rightchild = temp->rightchild->leftchild;
		 	 temp->rightchild->leftchild = temp;
		 
		 }
		 else    
		 	 rotateNode = rotateNode->leftchild;
		 	 temp->leftchild = temp->leftchild->rightchild;
		 	 temp->leftchild->rightchild = temp;	
	}//end Rotate function

};

int main( int argc, char* argv[] ){

	AVLTree *tree = new AVLTree();
	vector<string> avlvector;
	string input;
	ifstream argfile( "input.txt" );
	if( argfile.is_open() ){
		while( !argfile.eof() ){

			getline( argfile, input );
			avlvector.push_back(input);
		}
		argfile.close();

	}

	string s;
	
	int i = 0;
	string helper;
	char* number;
	int num;
      while( i < avlvector.size() ){
     	 s = avlvector.at(i);
      	 helper = s.substr(0,2);
      	 number = new char[helper.size() + 1 ];
      	 strcpy( number, helper.c_str() );
      	 num = atoi(number);
	 tree->AVLTreeInsert( num, s.substr(3,5));
	 i++;	   
      }
    
	
	while(1){}


}

you miss understand me.

this makes no sense, ok give me a few minutes, i will try to modify your code

AVLNode *temp = new AVLNode;
temp = this->root;
AVLNode *critNode = new AVLNode;
critNode = 0;
AVLNode *Rnode = new AVLNode;
Rnode = 0;

Kind of like this:

IS NOT Done, but i hope you get my point.

#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<fstream>
#include <stdlib.h> 

using namespace std;

struct AVLNode{
    public:
    int balance;
	int key;
	string data;
	AVLNode* leftchild;
	AVLNode* rightchild;


};

class AVLTree{

    public:
    AVLNode *root;
    
    /*
	*inserts a new node given the paramaters
    *in a the same fashion as a binary search tree
    *and then checks to see if AVL is violated
    * k is the key of the node which is an integer
    * d is the string for the info field
    * r is the root node of the AVL Tree
    */
    void AVLTreeInsert( int k, string d){
		
	    AVLNode *temp = this->root; 
        AVLNode *critNode = 0;
        AVLNode *Rnode = 0;
        bool critNodeFound = false;	 

	 cout << "what is up here" << endl;
        //cout << temp->key << endl;
	 cout << "i don't know" << endl;
	 	 
        while(  temp != NULL && temp->key != k ){
		
		    if( temp->balance != 0 ){
				critNode = temp;
				critNodeFound = true;
		    }
		    if( k < temp->key ){
				
			 	temp = temp->leftchild;
		    }
		    else
		        temp = temp->rightchild;
		}
		if(  temp != NULL ){
		
		    temp->data = d;
		    return;
		}
		
		/* NEW --------------------------------------------- */
		
		if( temp == NULL ){
		    AVLNode *newNode = new AVLNode();
		    
		    newNode->data = d;
		    newNode->key = k;
		    
		    temp = newNode;
		    
		    root = temp;
		}
		/* NEW end ------------------------------------------ */
		
		temp->data = d;
		temp->key = k;
		temp->leftchild = NULL;
		temp->rightchild = NULL;
		temp->balance = 0;
		
		if( !critNodeFound ){
			
			Rnode = this->root;
		}
		else{
            int d1;
            int d2;
            int d3;
            AVLNode *Cnode;
            AVLNode *Bnode;
            
            if( k == critNode->key ){
                d1 = 0;
                Cnode = critNode;
			}
            else if( k < critNode->key ){
                d1 = -1;
                Cnode = critNode->leftchild;
			}
            else{
                d1 = 1;
                Cnode = critNode->rightchild;
			}	
					
			
            if( critNode->balance != d1 ){
			   critNode->balance = 0;
               Rnode = temp;
		    }
		    else{
	            if( k == Cnode->key ){
	                d2 = 0;
	                Bnode = Cnode;
				}
	            else if( k < Cnode->key ){
	                d2 = -1;
	                Bnode = Cnode->leftchild;
				}
	            else{
	                d2 = 1;
	                Bnode = Cnode->rightchild;
				}
				if( d2 == d1 ){
				    critNode->balance = 0;
				    Rnode = Bnode;
				    rotate(critNode, -d1);
				
				}
				else{
		            if( k == Bnode->key ){
		                d3 = 0;
		                Rnode = Bnode;
					}
		            else if( k < Bnode->key ){
		                d3 = -1;
		                Rnode = Bnode->leftchild;
					}
		            else{
		                d3 = 1;
		                Rnode = Bnode->rightchild;
					}
					
					if( d3 = d2){
					    critNode->balance = 0;
					    Cnode->balance = d1;	
					}
					else if( d3 = -d2){
					    critNode->balance = d2;	 
		            }
		            else{
				        critNode->balance = 0;
					}
					rotate(Cnode, -d2);
					rotate(critNode, -d1);
				}
				 
		    }
		
		}
		while( Rnode->key != k ){
            if( k == Rnode->key ){
                Rnode->balance = 0;
                Rnode = Rnode;
			}
            else if( k < Rnode->key ){
                Rnode->balance = -1;
                Rnode = Rnode->leftchild;
			}
            else{
                Rnode->balance = 1;
                Rnode = Rnode->rightchild;
			}	   
        }
		
		
		
		
    }// end insert function
    
    
	void rotate( AVLNode *rotateNode, int d ){
		 
		 AVLNode *temp = rotateNode;
		 if( d == -1 ){
		 	 rotateNode = rotateNode->rightchild;
		 	 temp->rightchild = temp->rightchild->leftchild;
		 	 temp->rightchild->leftchild = temp;
		 
		 }
		 else    
		 	 rotateNode = rotateNode->leftchild;
		 	 temp->leftchild = temp->leftchild->rightchild;
		 	 temp->leftchild->rightchild = temp;	
	}//end Rotate function

};

int main( int argc, char* argv[] ){

	AVLTree tree;
	vector<string> avlvector;
	string input;
	ifstream argfile( "input.txt" );
	if( argfile.is_open() ){
		while( !argfile.eof() ){

			getline( argfile, input );
			avlvector.push_back(input);
		}
		argfile.close();

	}

	string s;
	
	int i = 0;
	string helper;
	char* number;
	int num;
      while( i < avlvector.size() ){
     	 s = avlvector.at(i);
      	 helper = s.substr(0,2);
      	 number = new char[helper.size() + 1 ];
      	 strcpy( number, helper.c_str() );
      	 num = atoi(number);
	 tree.AVLTreeInsert( num, s);
	 i++;	   
      }
    
	
	while(1){
	    sleep(1);
	}


}

You need to assign left and right child

commented: thanks for explaining it to me +3

Wow that fixed it, gonna make sure the rest of my logic is tight. So basically by ignoring the temp == null case, I was trying to access memory that wasn't there when I assinged values to temp after my temp != null case. Thank you I understand what I did wrong.

it's not quite right what i did, you need to create a new Node and sign the left anf right child, i sure you can do!

Yeah I did that, it was just the syntax I needed. I know how the logic works. Thank you.

Actually I realized just now with this logic, that the root will just constantly be replaced instead of children being put into the tree. But if I don't set the root there then I'll get seg faulted again. This is tough.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.