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

feels good don't it....

Don't wait till the night before next time you have to implement an AVL tree!!!

gg

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