-
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 :p
I have solved my problem :D
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
