AVL add

[mcrowder65]

I am writing an avl tree and when I insert numbers 0-50 and 0- (-50) it works perfectly. however, when i insert numbers -50 - 0 and 50-0 it crashes. has anybody dealt with this before? i'll post my code if someone replies! thanks!

[LB]

I'm driving a car and when I turn left then right then right then left, I get to my destination. However, when I turn right then left then left then right, it crashes. Has anyone dealt with this before?

We need to look at your car code.

[mcrowder65]

Node* AVL::rotate_left(Node* current)
{
	cout<<"rotating left"<<endl;
	if(root->balance < 1)
	{
	//	cout<<"returned"<<endl;
	//	return NULL;
	}
	Node* temp = current->right;
	current->right = temp->left;
	temp->left = current;	
	current = temp;
	//if(current->right->right != NULL)
	//	cout<<current->left->data<<" "<<current->data<<" "<<current->right->data<<" "<< current->right->right->data<<endl;
	return current;
}
Node* AVL::rotate_right(Node* current)
{
	cout<<"rotating right"<<endl;
	if(root->balance < 1)
	{
	//	cout<<"returned"<<endl;
	//	return NULL;
	}
	Node* temp = current->left;
	current->left = temp->right;
	temp->right = current;
	current = temp;
	return current;
}
Node* AVL::rebalance_right(Node* current)
{
	//cout<<"root balance: "<<root->balance<<endl;
	cout<<"rebalance right"<<endl;
	if(current->right->balance < 0) // 
	{
		if(current->right->left->balance > 0)
		{
			current->right->balance = 0;
			current->right->left->balance = 0;
			current->balance = -1;
		}
		else if(current->right->left->balance == 0) //figure this one out!
		{
			current->right->balance = 0;
			current->right->left->balance = 0;
			current->balance = 0;
		}
		else
		{
			current->right->balance = 1;
			current->right->left->balance = 0;
			current->balance = 0;
		}
		current->right = rotate_right(current->right);
		decrease = true;
	}
	else
	{
		current->balance = 0;
		current->right->balance = 0;
	}
	decrease = true;
	current = rotate_left(current);
}
Node* AVL::rebalance_left(Node* current)
{
	cout<<"rebalance left"<<endl;
	if(current->balance > 0)
	{
		if(current->left->right->balance < 0)
		{
			current->left->balance = 0;
			current->left->left->balance = 0;
			current->balance = 1;
		}
		else if(current->left->right > 0)
		{
			current->left->balance = -1;
			current->left->left->balance = 0;
			current->balance =0;
		}
		else
		{
			current->left->balance = 0;
			current->left->left->balance = 0;
			current->balance = 0;
		}
		current->left = rotate_left(current->left);
		decrease = true;
	}
	else
	{
		current->left->balance = 0;
		current->balance = 0;
	}
	decrease = true;
	current = rotate_right(current);
	return current;
}
bool AVL::add(int data)
{
	if(containsR(data, root) == false)
	{
		root = addR(root, data);
		cout<<"$$$$$$$$$$$$$$$$$$$$ added: "<<data<<endl;
		return true;
	}
	else
	{
		return false;
	}

}
Node* AVL::addR(Node* current, int data)
{
	if(current == NULL)
	{
		increase = false;
		return new Node(data, 0, 0, NULL, NULL);
	}
	else if(data == current->data)
	{
		return NULL;
	}
	else if(data < current->data)
	{
		current->left = addR(current->left, data);
		if(increase)
		{
			increase = false;
			current->balance = current->balance - 1;
		}
		current = balanceTree(current);
		return current;
	}
	else if(data > current->data)
	{
		current->right = addR(current->right, data);
		if(increase)
		{
			current->balance = current->balance + 1;
			increase = false;
		}
		current = balanceTree(current);	
		return current;
	}
}
int AVL::height(Node* current)
{
	if(current == NULL)
		return 0;
	else
		return 1 + max(height(current->left), height(current->right));
}
int AVL::max(int a, int b)
{
	return (a >= b)? a: b;
}
int AVL::get_balance(Node* current)
{
	if(current == NULL) 
	{
		return 0;
	}
	else 
	{
		return height(current->left) - height(current->right);
	} 
}
Node* AVL::balanceTree(Node* current)
{
	int heightDiff = get_balance(current);
	cout<<"1"<<endl;
	if(heightDiff > 1)
	{
		cout<<"2"<<endl;
		if(get_balance(current->left) > 0)
		{
			cout<<"3"<<endl;
			//current = rotate_LL(current);
			current = rebalance_left(current);
		}
		else
		{
			cout<<"4"<<endl;
			//current = rotate_LR(current);
			current = rotate_right(current);
		}
	}
	else if(heightDiff < -1)
	{
		cout<<"5"<<endl;
		if(get_balance(current->right) < 0)
		{
			cout<<"6"<<endl;
			//current = rotate_RR(current);
			current = rebalance_right(current);
		}
		else
		{
			cout<<"7"<<endl;
			//current = rotate_RL(current);
			//current = rotate_right(current);
			current = rotate_left(current);
		}
	}


	return current;

}

Node is a class that has pointers to its left and right children. also has a data member of it, and a balance member.

[LB]

Please edit your post and make sure that your code is [code]between code tags[/code] so that there is syntax highlighting and line numbers.