mavltree.hpp

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

#ifndef _AVLTREE_
#define _AVLTREE_

#include "mavlnode.hpp"

/****************************
 * The AVL Tree Iterator class
 ***************************/
template<class T>
class AVLIterator
{
	public:
		typedef AVLNode<T>* Link;
		typedef AVLIterator<T> iterator;

		AVLIterator();
		AVLIterator(Link new_link);
		virtual ~AVLIterator();

		virtual Link& getIterPtr(void);

		virtual bool operator==(iterator it);
		virtual bool operator!=(iterator it);
		virtual iterator operator++();
		virtual iterator operator++(int inc);
		virtual void operator--();
		virtual T& operator*();

	protected:
		Link link;
};

/****************************
 * The AVL Tree class
 ***************************/
template<class T, class Compare>
class AVLTree
{
	public:
		typedef AVLNode<T>* Link;
		typedef AVLIterator<T> iterator;

		/* constructor and destructor */
		AVLTree(void);
		virtual ~AVLTree(void);

		/* 
		 * public methods to allow users 
		 * DO "find", "change", "erase" and "insert" operations on AVL tree
		 */
		virtual iterator find(const T& item);
        virtual iterator change(const T& item, const T& new_item);
		virtual iterator insert(const T& item);
		//virtual void erase(iterator itr);
		virtual iterator erase(const T& item);
		virtual void clear(Link link);
		virtual bool empty(void);

		/* get the first and last element */
		virtual iterator begin(void);
		virtual iterator end(void);
		virtual iterator leftmost(void);
		virtual iterator rightmost(void);

		/* debug and validation */
		virtual void print(void);
		bool isAVLTree(){ return checkAVLTree(header->parent); }

	protected:
		Compare compare;
		Link header;
		unsigned node_count;

	private:
		/* debug and validation */
		virtual bool checkAVLTree(Link root);
		virtual int getHeight(Link root, int height, int& maxHeight);
		virtual void printTree(Link root, int depth, char* pos);

		/* insertion related CORE helper methods */
		virtual iterator insertItem(const T& item, Link parent, Link& child);
		virtual void insertLeaf(const T& item, Link parent, Link& child);
		virtual void fixAfterInsertion(Link ancestor, Link inserted);
		virtual void adjustPath(Link to, Link inserted);
		virtual void adjustLeftRight(Link ancestor, Link inserted);
		virtual void adjustRightLeft(Link ancestor, Link inserted);
		virtual void rotateLeft(Link x);
		virtual void rotateRight(Link x);

		/* deletion related CORE helper methods */
        virtual Link eraseNode(Link node, const T& item, bool& shorter);
		virtual Link leftBalance(Link node);
		virtual Link LL_rotate(Link node);
		virtual Link LR_rotate(Link node);
		virtual Link rightBalance(Link node);
		virtual Link RL_rotate(Link node);
		virtual Link RR_rotate(Link node);

		//virtual void deleteLink(Link& x);
		//virtual void prune(Link& x);

};

#endif