Recursion Proble,

This is a discussion on Recursion Proble, within the C++ Programming forums, part of the General Programming Boards category; I have created the following functionS for an AVL tree. There seems to be a problem with the recursion. Code: ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    94

    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
    simple is always an understatement.....

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,699
    >> 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
    Last edited by Codeplug; 04-16-2004 at 12:36 PM.

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    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.
    Last edited by sweets; 04-16-2004 at 01:27 PM.
    simple is always an understatement.....

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    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
    simple is always an understatement.....

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,699
    feels good don't it....

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

    gg

  6. #6
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    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
    simple is always an understatement.....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 03:58 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 03:19 PM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21