Thread: Recursion Proble,

I have created the following functionS for an AVL tree. There seems to be a problem with the recursion.

Code:

template <class T>
int AVLtree<T>::insertData (const T &data)
{
	AVLnode<T> *newNode;
	bool taller;

	if (!(newNode = new AVLnode<T>))
		return false;

	newNode -> right = NULL;
	newNode -> left = NULL;
	newNode -> balance = EH;
	newNode -> info = data;

	tree = insertHelper (tree, newNode, taller);
	count++;

	return true;
}

Code:

template <class T>
AVLnode<T>* AVLtree<T>::insertHelper(AVLnode<T>*root,AVLnode<T>*node,bool&higher)
{
	if (!root)
	{
		root = node;
		higher = true;
		return root;
	}

	if (node->info.ID < root->info.ID)
	{
		root->left = insertHelper (root, node, higher);  //<-- HERE
		if (higher)
		{
			switch (root->balance)
			{
				case LH:	root = leftBalance (root, higher);
							break;

				case EH:	root->balance = LH;
							break;

				case RH:	root->balance = EH;
							higher = false;
							break;
			}//switch
		}//if
	}//if
	else
	{
		root->right = insertHelper (root, node, higher); //<-- HERE
		if (higher)
		{
			switch ( root->balance)
			{
				case LH:	root->balance = EH;
							higher = false;
							break;

				case EH:	root->balance = RH;
							break;

				case RH:	root = rightBalance (root, higher);
							break;
			}//switch
		}//if
	}//else
	return root;
}

The recursion seems to end up in an endless loop and I cant see the problem. Can anyone help?

Thanx
Sophie

>> AVLnode<T>* AVLtree<T>::insertHelper(AVLnode<T>*root,AVLnode<T >*node,bool&higher)

"root" is a call-by-value parameter. The caller does not "see" any changes made to the pointer's value.

[EDIT]
that might not be the problem.....I'll have to look at after work
[/EDIT]

[EDITEDIT]
the only "exit" condition for the recursion is "if (!root)" and all the recursion call sites pass in root......if you think about it, you can see why it never ends
[/EDITEDIT]

gg

It's 04:10 here in Australia, and I guess I must be brain dead.
I have changed it to pass-by-reference and it works to a certain degree. I am having problems now with my rightBalance function

Code:

template <class T>
void AVLtree<T>::rightBalance (AVLnode<T> *&root, bool &higher)
{
	AVLnode<T> *rightTree, *leftTree;

	rightTree = root->right;

	switch (rightTree->balance)   
	{
		case LH:	root->balance = EH;
					rightTree->balance = EH;
					root = rotateLeft (root);
					higher = false;
					break;

		case EH:	cout << "Error in right balance";
					exit(100);

		case RH:	leftTree = rightTree->left;
					switch (leftTree->balance)
					{
						case LH:	root->balance = LH;
									rightTree->balance = EH;
									break;

						case EH:	root->balance = EH;
									rightTree->balance = RH;
									break;

						case RH:	root->balance = EH;
									rightTree->balance = RH;
									break;
					}//switch

					leftTree->balance = EH;
					root->right = rotateRight (rightTree);
					root = rotateLeft (root);
					higher = false;
	}//switch

}

I was told that it was a mirror of the balanceLeft function, which is as follows:

Code:

template <class T>
void AVLtree<T>::leftBalance (AVLnode<T> *&root, bool &higher)
{
	AVLnode<T> *rightTree, *leftTree;

	leftTree = root->left;

	switch (leftTree->balance)
	{
		case LH:	root->balance = EH;
					leftTree->balance = EH;
					root = rotateRight (root);
					higher = false;
					break;

		case EH:	cout << "Error in left balance";
					exit(100);

		case RH: rightTree = leftTree->right;
					switch (rightTree->balance)
					{
						case LH:	root->balance = RH;
									leftTree->balance = EH;
									break;

						case EH:	root->balance = EH;
									leftTree->balance = EH;
									break;

						case RH:	root->balance = EH;
									leftTree->balance = LH;
									break;
					}//switch

					rightTree->balance = EH;
					root->left = rotateLeft (leftTree);
					root = rotateRight (root);
					higher = false;
	}//switch
}

I pretty sure the balanceLeft fnct is correct....but I am not too sure of the balanceRight. Can anyone see anything wrong with it..because I keep getting a general exception error for it.

It is now 06:18.....and yes, being sleepless makes a person, both dumb and blind

I have solved my problem

The following is the correct rightBalance fnct:

Code:

template <class T>
void AVLtree<T>::rightBalance (AVLnode<T> *&root, bool &higher)
{
	AVLnode<T> *rightTree, *leftTree;

	rightTree = root->right;

	switch (rightTree->balance)
	{
		case LH: leftTree = rightTree->left;
					switch (leftTree->balance)
					{
						case LH:	root->balance = LH;
									rightTree->balance = EH;
									break;

						case EH:	root->balance = EH;
									rightTree->balance = EH;
									break;

						case RH:	root->balance = EH;
									rightTree->balance = RH;
									break;
					}//switch

					leftTree->balance = EH;
					root->right = rotateRight (rightTree);
					root = rotateLeft (root);
					higher = false;
					break;

		case EH:	cout << "Error in right balance";
					exit(100);

		case RH: root->balance = EH;
					rightTree->balance = EH;
					root = rotateLeft (root);
					higher = false;
					break;
	}//switch
}

My balanceLeft fnct also had a glitch, which I have corrected.

Code:

template <class T>
void AVLtree<T>::leftBalance (AVLnode<T> *&root, bool &higher)
{
	AVLnode<T> *rightTree, *leftTree;

	leftTree = root->left;

	switch (leftTree->balance)
	{
		case LH:	root->balance = EH;
					leftTree->balance = EH;
					root = rotateRight (root);
					higher = false;
					break;

		case EH:	cout << "Error in left balance";
					exit(100);

		case RH: rightTree = leftTree->right;
					switch (rightTree->balance)
					{
						case LH:	root->balance = RH;
									leftTree->balance = EH;
									break;

						case EH:	root->balance = EH;
									leftTree->balance = EH;
									break;

						case RH:	root->balance = EH;
									leftTree->balance = LH;
									break;
					}//switch

					rightTree->balance = EH;
					root->left = rotateLeft (leftTree);
					root = rotateRight (root);
					higher = false;
					break;
	}//switch
}

I will now get some well deserved sleep

Ohh no way of that ever happening. This is an ongoing project which isnt due until early June.

I just cant stop when I start and cant sleep if I dont solve any problems I have

Thanx again
Sophie