AVL

[sara khan]

#include <iostream.h>
#include "llstack.cpp"
#include <conio.h>

template<class T>
struct Node
{
	int rh;
	int lh;
	Node<T> *left;
	Node<T> *right;
	T info;
	Node()
	{
		rh = lh = 0;
		left = right = 0;
		info = 0;
	}
	Node(T val)
	{
		rh = lh = 0;
		left = right = 0;
		info = val;
	}
};
template<class T>
class AVL
{
	private:
		Node<T> *root;
   ////private functions
		int isEmpty();
		void display(Node<T> *p);
      int getHeight(Node<T> *p);
	public:
		AVL();
		void insertion(T val);
		void deletion(T val);
		void display();
      int getHeight();
};
void main()
{
   clrscr();
	AVL <int> a;
	a.insertion(100);
	a.insertion(20);
	a.insertion(10);
        a.display();
	getch();
}
template<class T>
int AVL<T> :: isEmpty()
{
	return root == 0;
}
template<class T>
void AVL<T>::display(Node<T>*p)
{
	if(p == 0)
	{
		return;
	}
//	if(p->left)
		display(p->left);
   cout<<" "<<p->info;
//   if(p->right)
	 display(p->right);
}
template<class T>
int AVL<T>:: getHeight(Node<T> *p)
{
	if(p == 0)
   {
   	return 0; 
   }
   int a = getHeight(p->left) +1;
   int b = getHeight(p->right)+1;
   return a+b;
}
template<class T>
AVL<T>::AVL()
{
	root = 0;
}
template<class T>
void AVL<T>::insertion(T val)
{
	if(isEmpty())
	{
		root = new Node<T> (val);
		return;
	}
	Node<T> *p = root;
	LLStack<Node<T> *> s;

	while(p != 0)
	{
		if(p->info < val)
		{
			if(p->right)
			{
				s.push(p);
				p = p->right;
			}
			else
			{
				s.push(p);
				p->right = new Node<T> (val);
				p = p->right;
				break;
			}
		}
		else if(p->info > val)
		{
			if(p->left)
			{
				s.push(p);
				p = p->left;
			}
			else
			{
				s.push(p);
				p->left = new Node<T> (val);
				p = p->left;
				break;
			}
		}
	}
	while(!s.isEmpty())
	{
		Node<T> * t = s.pop();
      if(t->left)
      {
			if(t->left->info == p->info)
			{
				if(p->lh > p->rh)
				{
					t->lh = p->lh + 1;
				}
				else if(p->lh == p->rh)
				{
					t->lh = p->lh + 1;
				}
				else if(p->lh < p->rh)
				{
					t->lh = p->rh + 1;
				}
         }
		}
      else if(p->right)
      {
			if(t->right->info == p->info)
			{
				if(p->lh > p->rh)
				{
					t->rh = p->lh + 1;
				}
				else if(p->lh == p->rh)
				{
					t->rh = p->lh + 1;
				}
				else if(p->lh < p->rh)
				{
					t->rh = p->rh + 1;
				}
			}
      }
	  if( (t->lh) - (t->rh) == 2)
		{
			int ll = 0 ,lr = 0;

			ll = t->left->lh;
			lr = t->left->rh;

			if(ll > lr)
			{
				Node<T> * P = t;
				Node<T> * LP;
				Node<T> * RLP;

			  if(t->left)
					LP =  t->left;
			  if(t->left->right)
					RLP = t->left->right;
			  if(RLP)
					P->left = RLP;
			   LP->right = P;
			   break;
			}
			else if(ll < lr)
			{
			   Node<T> * P = t;
				Node<T> * LP =  t->left;
				Node<T> * LRP = t->left->right;
				LP = P->right;
				LP->right = P;
				p->left = LRP;

			break;
			}
		}
		p = t;
	}
}
template<class T>
void AVL<T>::display()
{
	display(root);
}
template<class T>
int AVL<T>:: getHeight()
{
	return getHeight(root);
}

i m trying to do insertion in AVL but dont know how I can manage balance factor and my insertion is also not working properly...

plz help