AVL tree balancing problem

This is a discussion on AVL tree balancing problem within the C++ Programming forums, part of the General Programming Boards category; I have created an avl tree which seems to work if the information stored is only in the hundreds. The ...

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

    AVL tree balancing problem

    I have created an avl tree which seems to work if the information stored is only in the hundreds. The problem begins when the information to be stored in the tree is in the thousands. The tree gives me a balancing error.

    The problem occurs when it is balancing the tree to either the right or the left. When the rightBalance() or leftBalance() function is called the tree is suppose to be out of balance, therefore the balance variable should not be EH, it should be LH or RH.

    I cannot understand why this is occuring. I am thinking that there is some logical error which I cant see, so I am desperately in need of help.

    Thanx
    Sophie

    Code:
    const int LH = 1;  // left high
    const int EH = 0;  // equal high
    const int RH = -1; // right high
    
    template <class T>
    class AVLtree; 
    
    
    template <class T>
    struct AVLnode
    {
    	friend class AVLtree<T>;
    
    	T info;
    	int balance;
    	AVLnode<T> *right;
    	AVLnode<T> *left;
    
    	AVLnode () {right = left = NULL;}
    };
    //=============================================================================
    
    template <class T>
    class AVLtree
    { 
    	public:
    		AVLnode<T> *tree;
    		AVLtree () {tree=NULL;};
    		~AVLtree () {clear(tree);};
    		void insertData (const T &data);
    		void printAVLtree () {printInOrder(tree);};
    		T searchTree (T& data) {return (srchTreeHelper(tree, data));};
    
    	protected:
    		void clear (AVLnode<T> *tree);
    
    		AVLnode<T> * insertHelper (AVLnode<T> *root, AVLnode<T>*node, bool &higher, T data);
    		AVLnode<T> * rightBalance (AVLnode<T> *root, bool &higher);
    		AVLnode<T> * leftBalance (AVLnode<T> *root, bool &higher);
    
    		AVLnode<T>* rotateRight (AVLnode<T> *root);
    		AVLnode<T>* rotateLeft (AVLnode<T> *root);
    		void printInOrder (AVLnode<T> *root);
    		T srchTreeHelper (AVLnode<T> *treeRoot, T& data);
    
    };
    Code:
    //============================INSERT DATA======================================
    template <class T>
    void AVLtree<T>::insertData (const T &data)
    {
    	AVLnode<T> *newNode;
    	bool taller;
    
    	newNode = new AVLnode<T>;
    
    	
    	if (!(newNode=new AVLnode<T>))
    	{
    		cout << "memory problem";
    		exit (100);
    
    	}
    	newNode -> right = NULL;
    	newNode -> left = NULL;
    	newNode -> balance = EH;
    	newNode -> info = data;
    
    	tree=insertHelper (tree, newNode, taller, data);
    }
    
    //==========================INSERT HELPER======================================
    template <class T>
    AVLnode<T> * AVLtree<T>::insertHelper(AVLnode<T>*root, AVLnode<T>*node, bool &higher, T data)
    {
    	if (!root)
    	{
    		root = node;
    		higher = true;
    		return root;
    	}
    	else
    	{
    		data = node->info ;
    		if (data < root->info)
    		{
    			root->left=insertHelper (root->left, node, higher, data);
    
    			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;
    				}
    			}
    		}
    		else
    		{
    			root->right=insertHelper (root->right, node, higher, data);
    
    			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;
    				}
    			}
    		}
    	}
    	return root;
    }
    
    //==========================LEFT BALANCE=======================================
    template <class T>
    AVLnode<T> * 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";  // <-- HERE
    					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;
    					}
    
    					rightTree->balance = EH;
    					root->left = rotateLeft (leftTree);
    					root = rotateRight (root);
    					higher = false;
    					break;
    	}
    	return root;
    }
    
    //==========================RIGHT BALANCE======================================
    template <class T>
    AVLnode<T> * 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;
    					}
    
    					leftTree->balance = EH;
    					root->right = rotateRight (rightTree);
    					root = rotateLeft (root);
    					higher = false;
    					break;
    
    		case EH:	cout << "Error in right balance";   // <-- HERE
    
    					exit(100);
    
    		case RH: root->balance = EH;
    					rightTree->balance = EH;
    					root = rotateLeft (root);
    					higher = false;
    					break;
    	}
    	return root;
    }
    
    
    //==========================ROTATE LEFT========================================
    template <class T>
    AVLnode<T>* AVLtree<T>::rotateLeft (AVLnode<T> *root)
    {
    	AVLnode<T> *tmp;
    
    	tmp = root->right;
    	root->right = tmp->left;
    	tmp->left = root;
    
    	return tmp;
    }
    
    
    //==========================ROTATE RIGHT=======================================
    template <class T>
    AVLnode<T>* AVLtree<T>::rotateRight (AVLnode<T> *root)
    {
    	AVLnode<T> *tmp;
    
    	tmp = root->left;
    	root->left = tmp->right;
    	tmp->right = root;
    
    	return tmp;
    }
    simple is always an understatement.....

  2. #2
    Registered User
    Join Date
    May 2004
    Posts
    127
    My test works up to one million items. What data are you using and how are you manipulating the tree?

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    I am sending the tree an object that contains information such as :

    Essendon 3040 <-- This line is used as the key
    27234

    Essendon North 3041
    27235

    Essendon West 3040
    27236

    Eureka 3350
    27237

    Euroa 3666
    27238

    Eurobin 3739
    27239

    Evansford 3371
    27240

    Everton 3678
    27241

    Exford 3338
    27242

    The overloaded operator the tree is using is as follows:

    Code:
    int Dictionary::operator<(const Dictionary& diction)const
    {
    	return (_strnicmp(key, diction.key, strlen(diction.key))< 0); 
    }
    The tree works fine if the key is only numbers...but crashes otherwise.
    simple is always an understatement.....

  4. #4
    Registered User
    Join Date
    May 2004
    Posts
    127
    Still nothing. It works with a tree of up to one million items in the short tests I ran. I'm sorry, but I can't help very much if I can't reproduce the problem.

  5. #5
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    I have attached the txt file I am trying to store. Here is the dictionary struct. I keep getting the error at 8801.

    Code:
    const int LEN = 150;
    
    struct Dictionary 
    {
    	long ID;
    	char key[LEN];
    
    	friend ostream& operator <<(ostream& os, const Dictionary& diction);
    	int operator < (const Dictionary &diction) const;
    	int operator > (const Dictionary& diction) const;
    };
    
    //=============================================================================
    ostream& operator <<(ostream& os, const Dictionary& diction)
    {
    	os << diction.key << endl << diction.ID << endl;
    	return os;
    }
    
    //=============================================================================
    int Dictionary::operator<(const Dictionary& diction)const
    {
    	
    	return (_strnicmp(key, diction.key, strlen(diction.key))< 0); 
    }
    
    //=============================================================================
    int Dictionary::operator>(const Dictionary& diction)const
    {
    	return (_strnicmp(key, diction.key, strlen(diction.key))> 0); 
    }
    Attached Files Attached Files
    simple is always an understatement.....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Balancing A Binary Tree
    By mike_g in forum C Programming
    Replies: 5
    Last Post: 08-12-2008, 05:01 PM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  3. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 11:42 PM
  4. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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