AVL tree taking horribly long time to insert

[shakehar]

I have written a code to insert into avl and it takes over 15 minutes for my code to insert 1000000 random where as a sequential insert i.e 1 to 1000000 takes only 14000 microsec.
I cant figure what is wrong with my code ,can somebody have a look and help me out ?
main.cpp

int _tmain(int argc, _TCHAR * argv[])
{
	InputGenerator ip;
	int* numbers =(int*) malloc(1000000 *sizeof(int));
	ip.RandomInput(numbers,1000000);
	AVL *avlTree = (AVL *) malloc(1000000 * sizeof(AVL));
	AVL *root = NULL;

	*avlTree = AVL(numbers[0]);
	root = avlTree;
	
	int balanceFac = 0;
	clock_t Start, Time;
	Start = clock();
	for ( int input=1; input< 1000000;input++)
	{
		avlTree++;
		*avlTree = AVL(input);
		avlTree->Insert(avlTree, root);

		// check if rotation is required.
		AVL * tempNo=avlTree->GetParent();	
		AVL* node1=NULL;
		AVL* node2=NULL;
		AVL* node3=NULL;
		int balFac=0;
		int rCase=0;
		while(tempNo!=NULL)
		{
			balFac=avlTree->GetBalanceFactor(tempNo);
			if(balFac>1||balFac<-1)
				break;
			tempNo=tempNo->GetParent();
		}
		if(balFac>1||balFac<-1)
		{
			node1=tempNo;
			if(balFac>0)
			{
				node2=node1->GetLChild();
				balFac=avlTree->GetBalanceFactor(node2);
				if(balFac>0)
				{
					node3=node2->GetLChild();
					rCase=1;
				}
				else
				{
					node3=node2->GetRChild();
					rCase=3;
				}
			}
			else
			{
				node2=node1->GetRChild();

				balFac=avlTree->GetBalanceFactor(node2);
				if(balFac>0)
				{
					node3=node2->GetLChild();
					rCase=4;
				}
				else
				{
					node3=node2->GetRChild();
					rCase=2;
				}
			}
			root=avlTree->Rotation(node2,node3,root,rCase);
		}
	}
	


	Time = clock() - Start;
	cout<<"Running time : "<<Time<<endl;
	//cout<<current->tm_min<<":"<<current->tm_sec<<endl;
	//avlOps->InorderPrint(root);

	return 0;
}

AVL.h

class AVL
{
private:
	// pointers to parent & children of the node
	AVL* parent;
	AVL* l_child;
	AVL* r_child;

	int key; // value stored in the node
	int size; // size of the subtree with the node as root

public:
	enum RotationCase
	{
		LL=1,
		RR=2,
		LR=3,
		RL=4
	};
	AVL(int n);
	AVL();
	~AVL(void);
	//void insertIntoTree(int n, std::map<int,AVL> &avlTree);
	int GetKey() const{return key;}
	int GetSize()const{return size;}
	void SetParent(AVL *node){parent=node;}
	void SetLChild(AVL *node){l_child=node;}
	void SetRChild(AVL *node){r_child=node;}

	AVL* GetLChild(){return l_child;}
	AVL* GetRChild(){return r_child;}
	AVL* GetParent(){return parent;}


	int GetBalanceFactor(AVL* childNode); //Gets the balance factor of granfparent of just inserted node.
	int GetRotationCase(AVL* childNode); // returns what rotation method is to be followed.

	AVL* Rotation(AVL* parent,AVL* child, AVL *root,int rCase);
	AVL* LL_Rotation(AVL* childNode);//0 for rotating parent 1 for rotating the node
	AVL* RR_Rotation(AVL* childNode);
	//void LL_Rotation(AVL *pivotNode);

	void AVLInsert();

	void IncrementSize(){size=size+1;}
	AVL* Insert(AVL *node, AVL *root);
	bool Search(int n,AVL *root);
	int getHeight(AVL *node);
	void InorderPrint(AVL* root);

};

AVL.cpp

#include "stdafx.h"
#include "AVL.h"
#include <map>
#include <iostream>
#include <string>


using namespace std;

AVL::AVL(int n):key(n),parent(NULL),l_child(NULL),r_child(NULL),size(1)
{}

/*bool AVL::Insert(int n)
{
//FindParent(n);
}*/

AVL::AVL(){}

AVL::~AVL(void)
{
	//std::////cout<<"Destructing .."<<key<<std::endl;
}

AVL* AVL::Insert(AVL *node, AVL *root)
{
	if(node->GetKey() > root->GetKey()) // go right
	{

		if(root->GetRChild()==nullptr)
		{
			node->SetParent(root);
			root->SetRChild(node);
			return root;
		}
		else 
		{
			return Insert(node,root->GetRChild());
		}
	}
	else if(node->GetKey() < root->GetKey()) // go left
	{
		if(root->GetLChild()==nullptr)
		{
			node->SetParent(root);
			root->SetLChild(node);
			return root;
		}
		else {
			return Insert(node,root->GetLChild());
		}
	}
	else 
		return root;
}

int AVL::GetBalanceFactor(AVL* node)
{
	int l_side=0;
	int r_side=0;
	if(node->GetLChild()!=NULL)
	{
		l_side=getHeight(node->GetLChild());
	}
	if(node->GetRChild()!=NULL)
	{
		r_side=getHeight(node->GetRChild());
	}
	return l_side-r_side;
}

// returns the kind of inversion to be implemented
int AVL::GetRotationCase(AVL* childNode) 
{
	int invCase;
	AVL *parent=NULL;
	AVL* gParent=NULL;
	AVL * ggParent=NULL;
	parent=childNode->GetParent();
	if(parent!=NULL)
		gParent=parent->GetParent();
	if(gParent!=NULL)
		ggParent=gParent->GetParent();

	if(gParent->GetLChild()==parent && parent->GetLChild()==childNode)
		invCase=1;//LL
	else if(gParent->GetLChild()==parent && parent->GetRChild()==childNode)
		invCase=3;//LR
	else if(gParent->GetRChild()==parent && parent->GetRChild()==childNode)
		invCase=2;//RR
	else 
		invCase=4;

	return invCase;
}

AVL* AVL::Rotation(AVL* parent,AVL* child, AVL *root,int rCase) // this returns pointer of the root incase it changes
{
	////cout<<"Rotating... ";// bring in the node at which disbalance occurs and then operate from there
	AVL *tempRoot=NULL;
	////cout<<"rotation case is :";
	switch (rCase)
	{
	case LL:
		////cout<<"LL"<<endl;
		tempRoot=LL_Rotation(parent);
		break;
	case RR:
		////cout<<"RR"<<endl;
		tempRoot=RR_Rotation(parent);
		break;
	case LR:
		////cout<<"LR"<<endl;
		tempRoot=RR_Rotation(child);
		tempRoot=LL_Rotation(child);
		break;
	case RL:
		////cout<<"RL"<<endl;
		tempRoot=LL_Rotation(child);
		tempRoot=RR_Rotation(child);
		break;
	default:
		break;
	}
	if(tempRoot!=NULL)
		return tempRoot;// returns the new root of the tree
	else 
		return root;
}

AVL* AVL::LL_Rotation(AVL* node)
{
	AVL *root=NULL;
	AVL *parent=node;
	AVL *grandParent=NULL;
	AVL *beta=NULL;
	AVL * GGPArent=NULL;

	grandParent=(parent!=NULL? parent->GetParent():NULL);
	beta=(parent!=NULL?parent->GetRChild():NULL);
	GGPArent=(grandParent!=NULL?grandParent->GetParent():NULL); 

	if(GGPArent!=NULL)
	{
		if(GGPArent->GetLChild()==grandParent)
		{
			GGPArent->SetLChild(parent);// set pivot to point to the parent of grandParent
		}
		else 
		{
			GGPArent->SetRChild(parent);
		}
		parent->SetParent(GGPArent);
	}
	else 
	{
		root=parent;
		parent->SetParent(NULL);
	}
	parent->SetRChild(grandParent);//set grandParent as pivots right child
	grandParent->SetParent(parent);

	grandParent->SetLChild(beta);//set right child of pivot as left child of root
	if(beta!=NULL)
		beta->SetParent(grandParent);
	return root;
}

AVL* AVL::RR_Rotation(AVL* node)
{
	AVL *root=NULL;
	AVL *parent=node;
	AVL *grandParent=NULL;
	AVL *beta=NULL;
	AVL *GGPArent=NULL;


	grandParent=parent->GetParent();
	beta=parent->GetLChild();
	GGPArent=grandParent->GetParent(); // write func for when GGParent doesnot exist
	if(GGPArent!=NULL)
	{
		if(GGPArent->GetLChild()==grandParent)
		{
			GGPArent->SetLChild(parent);
		}
		else
		{
			GGPArent->SetRChild(parent);// set pivot to point to the parent of grandParent
		}
		parent->SetParent(GGPArent);
	}
	else 
	{
		root=parent;
		parent->SetParent(NULL);
	}
	parent->SetLChild(grandParent);//set grandParent as pivots right child
	grandParent->SetParent(parent);
	grandParent->SetRChild(beta);//set right child of pivot as left child of root
	if(beta!=NULL)
		beta->SetParent(grandParent);
	return root;
}
bool AVL::Search(int n,AVL *root)
{
	if(root->GetKey()>n)//go left
	{
		if(root->GetLChild()!=NULL)
			return Search(n,root->GetLChild());
		else 
			return false;
	}
	else if(root->GetKey()<n)//go right
	{
		if(root->GetRChild()!=NULL)
			return Search(n,root->GetRChild());
		else 
			return false;
	}
	else if (root->GetKey()==n)
		return true;
	else 
		return false;
}

int AVL::getHeight(AVL* node)
{ 
	int l=0;
	int r=0;
	if(node->GetLChild()!=NULL)
	{
		l= getHeight(node->GetLChild());
	}
	if(node->GetRChild()!=NULL)
	{
		r=getHeight(node->GetRChild());
	}
	return l>r?1+l:1+r;
}
void AVL::InorderPrint(AVL* root)
{
	if(root->GetLChild()==NULL)
	{
		cout<<root->GetKey()<<" ";
	}
	else
	{
		InorderPrint(root->GetLChild());
		cout<<root->GetKey()<<" ";
	}
	if(root->GetRChild()!=NULL)
	{
		InorderPrint(root->GetRChild());
	}
}

void AVLInsert()
{

}