PROGRAM TO GENERATE AVL TREE AND FIND ITS DEPTH.

#include <iostream.h>         //HEADER FILES
 #include <fstream.h>
 #include <stdio.h>

struct node                       //STRUCTURE FOR TREE NODE
 {
 int data;
 int leftheight,rightheight;
 struct node *father;
 struct node *left,*right;
 };
 fstream fp;
 int dup=0;
 class tree                            //CLASS TREE
 {
 public :
 struct node * root;
 tree()
 {
 root=NULL;
 }
 void input ()                      //FUNCTIONS DEFINED INLINE
 {
 int temp;
 fp.open("datab2.txt",ios::in);
 while(fp>>temp)
 add (temp);
 }
 struct node * create (int y)
 {
 struct node * temp=new node ;
 temp->data=y;
 temp->father=NULL;
 temp->left=temp->right=NULL;
 temp->leftheight=temp->rightheight=0;
 return temp;
 }
 void add (int a)
 {
 struct node *x,*y,*z;
 struct node * temp= search(a,root);
 x=y=z=NULL;
 if (temp==NULL)
 root=create (a);
 else if (temp->data!=a)
 {
 x=create(a);
 if (temp->data>a)
 temp->left=x;
 else
 temp->right= x;
 x->father=temp;
 while(x!=NULL)
 {
 z=y;
 y=x;
 x=x->father;
 if (x!=NULL )
 {
 update(x);
 if (check(x))
 rearrange(x,y,z);
 }
 }
 }
 else
 {
 cout<<a<<" ";
 dup++;
 }
 }
 int maxheight(struct node * p)
 {
 if (p==NULL)
 return -1;
 if (p->leftheight > p->rightheight)
 return p->leftheight;
 return p->rightheight;
 }
 int mod (int a,int b)
 {
 if(a>b)
 return a-b;
 else
 return b-a;
 }
 int check(node * a)
 {
 if(mod (a->leftheight,a->rightheight)<2)
 return 0;
 return 1;
 }
 void rearrange(struct node * a ,struct node * b,struct node * c)
 {
 if((a->data > b->data)&&(b->data > c->data)||(a->data<b->data)&&(b->data<c->data))
 singlerotation (a,b);
 else
 doublerotation(a,b,c);
 }
 void singlerotation (struct node * a,struct node * b)
 {
 if (a->data < b->data)
 {
 a->right=b->left;
 if (b->left!=NULL)
 b->left->father=a;
 b->left=a;
 }
 else
 {
 a->left=b->right;
 if (b->right!=NULL)
 b->right->father=a;
 b->right=a;
 }
 if ((b->father=a->father)!=NULL)
 {
 if( a->father->right==a)
 a->father->right=b;
 else
 a->father->left=b;
 }
 else
 root=b;
 a->father=b;
 update (a);
 update (b);
 }
 void doublerotation(struct node * a,struct node * b,struct node * c)
 {
 singlerotation(b,c);
 singlerotation(a,c);
 update(a);
 update(b);
 update(c);
 }
 void update(struct node * p)
 {
 p->leftheight=maxheight(p->left)+1;
 p->rightheight=maxheight(p->right)+1;
 }
 struct node * search (int x,struct node * r)
 {
 while (1)
 {
 if (r==NULL)
 return NULL;
 else
 {
 if (x==r->data)
 break;
 else if(x>r->data)
 {
 if(r->right==NULL)
 break ;
 else
 return search (x,r->right);
 }
 else
 {
 if (r->left==NULL)
 break;
 else
 return search(x,r->left);
 }
 }
 }
 return r;
 }

void printnode (struct node * y)
 {
 cout<<y->data<<"  "<<y->leftheight <<" "<<y->rightheight<<endl;
 }

void output()
 {
 cout<<"\n No of duplicates="<<dup;
 cout<<"\n Depth of AVL tree="<<maxheight(root)<<endl;

}

void dump(struct node **base)         //TO FREE ALL ALLOCATED MEMORY
 {
 if(*base==NULL)
 return;
 if((*base)->left==NULL && (*base)->right==NULL)
 {
 delete(*base);
 *base=NULL;
 }
 else
 {
 dump(&((*base)->left));
 dump(&((*base)->right));
 dump(base);
 }
 }
 };

void main ()
{

tree t;
t.input();
t.output();
t.dump(&(t.root));
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s