Avl Tree

[waqifti]

I Am trying to Implement the avl tree in a different manner I would Like Ur Help and where Am i going wrong

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<windows.h>

#include <stdlib.h>

void gotoxy(int x, int y)
{
	HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

	_COORD pos;
	pos.X = x;
	pos.Y = y;

	SetConsoleCursorPosition(hConsole, pos);
}


class node
{
public:
	int data;
	int bfactor;
	node * left;
	node * right;

	node()
	{
		bfactor=0;
		data=0;
		left=NULL;
		right=NULL;
	}
};


 node * temp=NULL;
 int level=0;
 int bfactor1=0;
class AVLTree
{
public:
	node * root;

	AVLTree()
	{ root=NULL; }


	node * LocateParent(int Data,node *Root)
	{
	 node *pNode=Root,*pParent=NULL;
	 
	 while(pNode!=NULL && pNode->data!=Data)
	 {
	  pParent=pNode;
	  if(pNode->data<Data)
	   pNode=pNode->right;
	  else
	   if(pNode->data>Data)
		pNode=pNode->left;
	 }
	 return pParent;
	}
	
	void create()
	{

		for(;;)
		{
		cout<<" Enter a Number ";
		int a;
		cin>>a;

		insert(root,a);
		cout<<"\n Enter More (1/0) ";
		cin>>a;

		int stage = 3;
		int v=(stage-1)*10;

		set_bf(root);

		gotoxy(0,v); cout<<"++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
		display2(0,v+1);
		stage++;

		
		
			for(int z=0;z<1;)
			{
				int check=0;
				node * p,*parent;

				check_bf(root,check,level);

				p=temp;

				level=0;
				bfactor1=0;
				temp=NULL;				
				
				
				if(p!=NULL)
				{
					parent=LocateParent(p->data,root);					

					if(check<0)
					{
						gotoxy(0,(stage-2)*10);
						cout<<"Rotating RIGHT at node"<<p->data<<endl;
						if(parent==NULL)
						root=rotatetoright(p);
						else
						{
							if(parent->right->data==p->data)
							parent->right=rotatetoright(p);
							else
							{
								parent->left=rotatetoright(p);
							}
						}
					}
					else
					{
						gotoxy(0,(stage-2)*10);
						cout<<"Rotating LEFT at node"<<p->data<<endl;
						if(parent==NULL)
						root=rotatetoleft(p);
						else
						{
							if(parent->right->data==p->data)
							parent->right=rotatetoleft(p);
							else
							{
								parent->left=rotatetoleft(p);
							}
						}						
					}					
				}
				else
				{ z=1; }
				set_bf(root);

				v=(stage-1)*10;

				gotoxy(0,v); cout<<"++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
				display2(0,v+1);
				stage++;
			}

			v=(stage-1)*10;

			gotoxy(0,v); cout<<"++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
				display2(0,v+1);
				stage++;		
			cout.flush();
			cout<<endl;

			gotoxy(0,5);
			system("pause");
			system("cls");
			if(a!=1) break;		
		}
		
	}


	void insert(node * &x,int temp)
	{	
		if(x==NULL)
		{
			x=new node;
			x->data=temp;
			return;
		}
		
		/*if(x->data==temp)
		{
			cout<<"\n NO DUPLICATES ALLOWED :) "<<endl;
			return;
		}*/

		else
		{
			if(x->data>temp)
				insert(x->left,temp);
			else
				insert(x->right,temp);
		}	
	}

 
 


	node * rotatetoleft(node * & Root)
	{	
		//cout<<"Roatating LEFT at node"<<Root->data<<endl;

		 node * newroot;

		 newroot=Root->right;
		  Root->right=NULL;
		 
		 if(newroot->left==NULL)
		 {			 
			 newroot->left=Root;
		 }
		 else
		 {			
			node * temp=newroot;
			for(;temp->left!=NULL;)
			{
				temp=temp->left;
			}
			temp->left=Root;
		 }

		 return newroot;
		 
		   

		/*node *nw=Root;

		node * n;
		n=nw->right;
		nw->right=n->left;
		n->left=nw;
		nw=n;
		return nw;*/

			
	}

	node * rotatetoright(node * & Root)
	{
		//cout<<"Roatating Right at node"<<Root->data<<endl;
		
		node * newroot;

		 newroot=Root->left;
		 Root->left=NULL;		 

		 if(newroot->right==NULL)
		 {			 
			 newroot->right=Root;
		 }
		 else
		 {			
			node * temp=newroot;
			for(;temp->right!=NULL;)
			{
				temp=temp->right;
			}
			temp->right=Root;
		 }

		 return newroot;

		/*node *nw=Root;

		node * n;
		n=nw->left;
		nw->left=n->right;
		n->right=nw;
		nw=n;
		return nw;*/
	}

	
	
	int height1(node * p)
	{
        class node * temp=p;
        
		int h1=0,h2=0;
        if(p==NULL) return(0);
        if(p->left)
		{
			h1=height1(p->left);
		}

       if(p->right)
	   {
		   h2=height1(p->right);
	   }

        return(max(h1,h2)+1);
	}

	void check_bf(node * Root,int & check,int lvl)
	{		
		if(Root!=NULL )
		{	
							check_bf(Root->left,check,++lvl);

				check_bf(Root->right,check,++lvl);	

				if(Root->bfactor<-1 || Root->bfactor>1)
				{
					if(lvl>=level)
					{
						if(Root->bfactor<-1) check=-1;
						if(Root->bfactor>1) check=1;						
						temp=Root;
						bfactor1=check;
						level=lvl;
					}
				}				
		}
	}

	void set_bf(node * Root)
	{
		if(Root!=NULL)
		{			
		set_bf(Root->left);		
		
		Root->bfactor=height1(Root->right)-height1(Root->left);		

		set_bf(Root->right);				
		}
	}



	
	void display2(int x,int y)
	{		
		display(root,0,x,y);
	}

	void display(node * Root,int lvl,int &x,int y)
	{
		if(Root!=NULL)
		{
			y++;
		display(Root->left,lvl++,x,y);	
		
		gotoxy(x,y);
		cout<<y-1<<"L"<<Root->bfactor<<"BF";

	
		cout<<Root->data<<"D";		
		
		if(LocateParent(Root->data,root)!=NULL)
		{
			cout<<LocateParent(Root->data,root)->data<<"P";
		}
		cout<<endl;
		x=x+7;

		display(Root->right,lvl++,x,y);				
		}
	}
	int getheight()
	{
		return height1(root);
	}

	void print()
	{
		int x=0,y=0;

		for(;y<5;)
		{
		display2(x,y*10);
		y++;
		}

	}
};

void main()
{
		AVLTree A;
		A.create();

		



}

The Tree Doesnot balance properly at some stages and most of all it breaks rules for being a BS tree ( i.e this is a avl tree along with being a bs tree)

[codekiddy]

Oh men, I still don't have "code-formating-glasses"

use [code] [\code] tags.

[waqifti]

Please My Exam Tommorow

[codekiddy]

You didn't describe what errors are you receiving?

also your main function must be int main() not void main() and thus return an int.

also your main function must do something useful if you wann "see" some action :)