Thread: 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;
}

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.

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); 
}