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){}
}