mavltree.cpp

AVL Tree implementation: I also included a test function to compare the AVL Tree performance with S

{
	if (root != NULL)
	{
		if (root->visitFlag == 'N')
		{
			if (height > maxHeight)
				maxHeight = height;

			return maxHeight;
		}
		else
		{
			if (!root->left && !root->right)
				root->visitFlag = 'N';
			else
				root->visitFlag = 'V';

			height++;
		}

		if (root->left && root->left->visitFlag != 'N')
			getHeight(root->left, height, maxHeight);
		else
			if (height > maxHeight)  maxHeight = height;
		
		if (root->right && root->right->visitFlag != 'N')
			getHeight(root->right, height, maxHeight);
		else
			if (height > maxHeight)  maxHeight = height;
	}

	return maxHeight;
}

template<class T, class Compare>
void AVLTree<T, Compare>::print()
{
	cout << "Header item: " << header->item << endl;
	cout << "Header left: " << header->left->item << endl;
	cout << "Header right: " << header->right->item << endl;
	cout << "header's PARENT is: " << header->parent << endl;

	if (header->parent && header->parent->left && header->parent->right)
	{
		cout << "Root parent " << header->parent->item << endl;
		cout << "Root parent left " << header->parent->left->item << endl;
		cout << "Root parent right " << header->parent->right->item << endl;

		printTree(header->parent, 0, "[ROOT]");
	}
	
	cout << "Total nodes: " << node_count << endl;
}

template<class T, class Compare>
void AVLTree<T, Compare>::printTree(Link root, int depth, char* pos)
{
	if (root != NULL) {
		printTree(root->left, ++depth, "left");  // print left subtree

		cout << "[depth] : " << depth << " [pos] : " << pos << " [val] : " 
			 << root->item << " [bal] : " << root->balanceFactor 
			 << " [parent] : " << root->parent->item << endl; // print this node

		printTree(root->right, ++depth, "right"); // print right subtree
    }
}

template <class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::find(const T& item)
{
	Link parent = header;
	Link child = header->parent;

	while (child != NULL)
	{
		if (!compare(child->item, item)) //the former >= the latter
		{
			//if item to find is less than the searched item
			//keep going leftward and store the searched item in parent
			parent = child;
			child = child->left;
		}
		else
		{   
			//if the item to find is greater than the searched item
			//keep going rightward
			child = child->right;
		}
	}//while

	if (parent == header || compare(item, parent->item))
		return end();
	else
		return iterator(parent);
}//find()

template <class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::change(const T& item, const T& new_item)
{
	iterator found = find(item);
	
	if (found != end())
	{
		*found = new_item;

		/*//find the ancestor
		Link ancestor = NULL;
		Link child = found.getIterPtr();

		Link parent = child->parent;

		while (parent != NULL && parent != header)
		{
			if (parent->balanceFactor != '=')
			{
				ancestor = parent;
				break;
			}

			parent = parent->parent;
		}
		
		//update the tree structure
		fixAfterInsertion(ancestor, child);*/
	}
	
	return found;
}


/* 
 * =======================
 * INSERT related methods  
 * =======================
 */
template <class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::insert(const T& item)
{
	//inserting at the tree's root
	if (header->parent == NULL)
	{
		insertItem(item, header, header->parent);
		header->left = header->parent;
		header->right = header->parent;

		//cout << "End insert when header->parent = NULL" << endl;

		return iterator(header->parent);
	}
	else
	{
		//get the ancestor and parent
		Link parent = header;
		Link child = header->parent;
		Link ancestor = NULL;

		while (child != NULL)
		{
			parent = child;

			//get the deepest ancestor node
			//when its balance factor is 'L' or 'R'
			if (child->balanceFactor != '=')
				ancestor = child;

			//recrusively traverse into the deep tree
			if (compare(item, child->item))
				child = child->left;
			else
				child = child->right;
		}//while

		/*debugging***********************************************************
		if (ancestor != NULL)
			cout << "get the ancestor node value: " << ancestor->item << endl;
		else
			cout <<"!!!!!!!!!!Get the ancestor node value: NULL" << endl;
		//********************************************************************/

		if (compare(item, parent->item))
		{
			insertItem(item, parent, parent->left);
			fixAfterInsertion(ancestor, parent->left);

			if (header->left == parent)
				header->left = parent->left; //child is leftmost
			
			return iterator(parent->left);
		}//insert at left of parent
		else
		{
			insertItem(item, parent, parent->right);
			fixAfterInsertion(ancestor, parent->right);

			if (header->right == parent)
				header->right = parent->right; //child is rightmost

			return iterator(parent->right);
		}//insert at right of parent
	}//tree not empty
}//insert()


template <class T, class Compare>
void AVLTree<T, Compare>::fixAfterInsertion(Link ancestor, Link inserted)
{
	if (inserted == NULL)  return ;

	Link root = header->parent;
	T item = inserted->item;

	//Case 1: all ancestor's balance factors are '='
	if (ancestor == NULL)
	{
		//cout << "Case 1 start" << endl;
		if (compare(item, root->item))
			root->balanceFactor = 'L';
		else
			root->balanceFactor = 'R';

		adjustPath(root, inserted);
		//cout << "Case 1 end" << endl;
	}
	//Case 2: Insertion in opposite subtree of ancestor's balance factor
	else if ((ancestor->balanceFactor == 'L' && 
			!compare(item, ancestor->item)) ||  
			(ancestor->balanceFactor == 'R' && 
			compare(item, ancestor->item)))
	{
		//cout << "Case 2 start" << endl;
		ancestor->balanceFactor = '=';
		adjustPath(ancestor, inserted);
		//cout << "Case 2 end" << endl;
	}
	//Case 3: Insertion in right subtree of ancestor's right subtree
	else if (ancestor->balanceFactor == 'R' && 
			!compare(item, ancestor->right->item))
	{
		//cout << "Case 3 start" << endl;
		ancestor->balanceFactor = '=';
		rotateLeft(ancestor);
		adjustPath(ancestor->parent, inserted);
		//cout << "Case 3 end" << endl;
	}
	//Case 4: insertion in left subtree of ancestor's left subtree
	else if (ancestor->balanceFactor == 'L' && 
			compare(item, ancestor->left->item))
	{
		//cout << "Case 4 start" << endl;
		ancestor->balanceFactor = '=';
		rotateRight(ancestor);
		adjustPath(ancestor->parent, inserted);
		//cout << "Case 4 end" << endl;
	}
	//Case 5: insertion in right subtree of ancestor's left subtree
	else if (ancestor->balanceFactor == 'L' && 
			!compare(item, ancestor->left->item))
	{
		//cout << "Case 5 start" << endl;
		rotateLeft(ancestor->left);
		rotateRight(ancestor);
		adjustLeftRight(ancestor, inserted);
		//cout << "Case 5 end" << endl;
	}
	//Case 6: Insertion in left subtree of ancestor's right subtree
	else
	{
		//cout << "Case 6 start" << endl;
		rotateRight(ancestor->right);
		rotateLeft(ancestor);
		adjustRightLeft(ancestor, inserted);
		//cout << "Case 6 end" << endl;
	}
}//method fixAfterInsertion

template <class T, class Compare>
void AVLTree<T, Compare>::adjustPath(Link to, Link inserted)
{
	//cout << "adjustPath start" << endl;

	T item = inserted->item;
	Link temp = inserted->parent;

	while(temp != to && temp != header)
	{
		//cout << " I am stuck here ... " << endl;
	    //cout << "inserted = " << inserted->item << " temp = " << temp->item << " to = " << to->item << endl;
		if (compare(item, temp->item))
			temp->balanceFactor = 'L';
		else
			temp->balanceFactor = 'R';

		temp = temp->parent;
	}//while

	//cout << "adjustPath end" << endl;
}//method adjustPath


template <class T, class Compare>
void AVLTree<T, Compare>::adjustLeftRight(Link ancestor, Link inserted)
{
	//cout << "adjustLeftRight start" << endl;

	if (inserted == NULL || ancestor == NULL)  return ;

	T item = inserted->item;

	if (ancestor->parent == inserted) //a
		ancestor->balanceFactor = '=';
	else if (compare(item, ancestor->parent->item)) //b
	{
		ancestor->balanceFactor = 'R';
		adjustPath(ancestor->parent->left, inserted);
	}//item "<" ancestor's parent's item
	else //c
	{
		ancestor->balanceFactor = '=';
		ancestor->parent->left->balanceFactor = 'L';
		adjustPath(ancestor, inserted);
	}//item ">=" ancestor's parent's item
	//cout << "adjustLeftRight end" << endl;
}//method adjustLeftRight

template <class T, class Compare>
void AVLTree<T, Compare>::adjustRightLeft(Link ancestor, Link inserted)
{
	//cout << "adjustRightLeft start" << endl;

	if (inserted == NULL || ancestor == NULL)  return ;

	T item = inserted->item;

	if (ancestor->parent == inserted) //a
		ancestor->balanceFactor = '=';
	else if (!compare(item, ancestor->parent->item)) //b
	{
		ancestor->balanceFactor = 'L';
		adjustPath(ancestor->parent->right, inserted);
	}//item ">=" ancestor's parent's item
	else //c
	{
		ancestor->balanceFactor = '=';
		ancestor->parent->right->balanceFactor = 'R';
		adjustPath(ancestor, inserted);
	}//item "<" ancestor's parent's item
	//cout << "adjustRightLeft end" << endl;
}//method adjustRightLeft


template <class T, class Compare>
void AVLTree<T, Compare>::rotateLeft(Link x)
{
	//cout << "rotateLeft start" << endl;

	if (x == NULL || x->right == NULL)
	{
		cout << "skipping ... ... " << endl;
		return ;
	}

	Link y = x->right;  //*
	x->right = y->left; //*
	
	if (y->left != NULL)
		y->left->parent = x;
	
	y->parent = x->parent;

	if (x == header->parent) //if x is the root
		header->parent = y;
	else if (x == x->parent->left) //if x is a left child
		x->parent->left = y;
	else 
		x->parent->right = y;

	y->left = x;        //*
	x->parent = y;
	//cout << "rotateLeft end" << endl;
}

template <class T, class Compare>
void AVLTree<T, Compare>::rotateRight(Link x)
{
	//cout << "rotateRight start" << endl;

	if (x == NULL || x->left == NULL)
	{
		cout << "skipping ... ... " << endl;
		return ;
	}

	Link y = x->left;   //*
	x->left = y->right; //*

	if (y->right != NULL)
		y->right->parent = x;

	y->parent = x->parent;

	if (x == header->parent) //if x is the root
		header->parent = y;
	else if (x == x->parent->right) //if x is a right child
		x->parent->right = y;
	else
		x->parent->left = y;

	y->right = x;       //*
	x->parent = y;
	//cout << "rotateRight end" << endl;
}

template <class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::insertItem(const T& item, Link parent, Link& child)
{
	if (child == NULL)
	{
		insertLeaf(item, parent, child);

		//item "<" header->left->item
		if (compare(item, header->left->item))
			header->left = child;

		//item ">=" header->right->item
		if (!compare(item, header->right->item))
			header->right = child;

		return iterator(child);
		//return child;
	}

	//item "<" child->item, recursively insert at left
	if (compare(item, child->item))
		return insertItem(item, child, child->left);

	//item ">=" child->item, recursively insert at right
	return insertItem(item, child, child->right);
}//method insertItem


template <class T, class Compare>
void AVLTree<T, Compare>::insertLeaf(const T& item, Link parent, Link& child)
{
	child = new AVLNode<T>;
	child->item = item;
	child->parent = parent;
	child->left = NULL;
	child->right = NULL;
	child->isHeader = false;
	child->balanceFactor = '=';
	node_count++;
}//insertLeaf



/*
 * AVLTree::Iterator Methods declaration
 */
template <class T>
AVLIterator<T>::AVLIterator(Link new_link) : link(new_link)
{}


template<class T>
AVLIterator<T>::~AVLIterator()
{}


template<class T>
AVLIterator<T> AVLIterator<T>::operator++()
{
	Link tempLink;

	//node has right child
	if ((link->right) != NULL)
	{
		link = link->right;
		while ((link->left) != NULL)
		{
			link = link->left;
		}
	}
	//node has no right child
	else
	{
		//moving up and leftward as far as possible
		tempLink = link->parent;
		while (link == tempLink->right)
		{
			link = tempLink;
			tempLink = tempLink->parent;
		}

		if ((link->right) != tempLink)
			link = tempLink;
	}

	return *this;
}//prefix++

template<class T>
AVLIterator<T> AVLIterator<T>::operator++(int inc)
{
	/*Link tempLink;*/

	return *this;
}

template<class T>
void AVLIterator<T>::operator--()
{
	//return *this;
}

template<class T>
T& AVLIterator<T>::operator*()
{
	return link->item;
}

template<class T>
bool AVLIterator<T>::operator!=(iterator it)
{
	return (it.link != link);
}

template<class T>
bool AVLIterator<T>::operator==(iterator it)
{
	return (it.link == link);
}

template<class T>
AVLNode<T>*& AVLIterator<T>::getIterPtr()
{
	return link;
}