Posts Tagged depth

#include <iostream.h>        //INCLUDING REQUIRED LIBRARIES
#include <stdio.h>
#include<stdlib.h>

struct node                    //DECLARATION OF THE NODES OF THE AVL TREE
{
int data;                    //TO STORE THE NUMBER
int leftdepth,rightdepth;    //TO KEEP TRACK OF THE LEFT AND RIGHT DEPTH
struct node *father;
struct node *left,*right;    //POINTER TO THE LEFT AND RIGHT CHILD OF THAT NODE
};
class tree                        //DECLARING THE CLASS TREE
{
private :
struct node * root;
public :
tree()                    //ZERO-ARGUMENT CONSTRUCTOR
{
root=NULL;                //MAKING ROOT NULL
}
void input ()
{
int  temp;
FILE * ifp=fopen("int.txt","r");        //OPENING THE FILE CONTAINING 10000 RANDOM INTEGERS
while(fscanf(ifp,"%d",&temp)!=EOF)        //TILL THE END OF FILE
{
add (temp);                        //CALLING FUNCTION TO ADD THE NUMBER TO THE AVL TREE
}
}
struct node * create (int y)            //FUNCTION TO CREATE A NODE CONTAINING THE NUMBER
{
struct node * temp=new node ;
temp->data=y;                        //PUTTING THE DATA IN THE NEW NODE
temp->father=NULL;                    //MAKING FATHER NULL
temp->left=temp->right=NULL;        //MAKING RIGHT AND LEFT CHILD NULL
temp->leftdepth=temp->rightdepth=0;    //MAKING LEFT AND RIGHT depth EQUAL TO ZERO
return temp;                        //RETURNING THE NODE
}
void add (int a)                        //FUNCTION TO PUT THE NO IN THE NODE AND
//THEN ATTACH IT TO THE AVL TREE AT THE PROPER PLACE
{
struct node * curr= search(a,root),*x,*y,*z;
//CURR IS A POINTER TO THE NODE WHERE THE NEW NODE WILL BE ATTACHED
x=y=z=NULL;
if (curr==NULL)  root=create (a);    //IF NO ELEMENT IN THE TREE
else if (curr->data!=a)
//CREATING A NODE IF THE NO IS NOT EQUAL TO THE NO PRESENT IN THE CURRENT NODE AND ATTACHING IT TO THE BINARY TREE AT APPROPRIATE PLACE
{
x=create(a);
if (curr->data>a) curr->left=x;
else    curr->right= x;
x->father=curr;                //MAKING CURRENT NODE TO BE FATHER OF NEW NODE
while(x!=NULL)
{
z=y;
y=x;
x=x->father;
if (x!=NULL )
{
updatedepth(x);
if (check(x))        //***CALLING FUNCTION TO SATISFY THE AVL BALANCING CONDITION
rearrange(x,y,z);
}
}
}
else cout<<a<<"\t";
}
int maxdepth(struct node * p)        //RETURNING THE MAXIMUM DEPTH AT EACH NODE
{
if (p==NULL)
return -1;
if (p->leftdepth > p->rightdepth)
return p->leftdepth;
return p->rightdepth;
}
int mod (int a,int b)            //TO ADJUDGE WHETHER A SINGLE OR DOUBLE ROTATION IS REQUIRED
{
if(a>b)
return a-b;
else
return b-a;
}
int check(node * a)            //***FUNCTION TO CHECK IF THE AVL BALANCING CONDITION IS SATISFIED
{
if(mod (a->leftdepth,a->rightdepth)<2)
return 0;
return 1;
}
void rearrange(struct node * a ,struct node * b,struct node * c)
//FUNCTION TO REARRANGE THE NODES TO MAINTAIN THE AVL BALANCE
{
if( ((a->data - b->data) * (b->data -c->data)) > 0 )
singlerotation (a,b);
else
doublerotation(a,b,c);
}
//FUNCTION TO GIVE NODES SINGLE ROTATION SO THAT THE BALANCING CONDITION OF THE AVL TREE IS SATISFIED
void singlerotation (struct node * a,struct node * b)
{                    //FUNCTION TO DO SINGLEROTATION AT THE NODES
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;
updatedepth (a);
updatedepth (b);
}
//FUNCTION TO GIVE NODES DOUBLE ROTATION SO THAT THE BALANCING CONDITION OF THE AVL TREE IS SATISFIED
void doublerotation(struct node * a,struct node * b,struct node * c)
{        //FUNCTION TO DOUBLE ROTATION OF THE NODES
singlerotation(b,c);
singlerotation(a,c);
updatedepth(a);
updatedepth(b);
updatedepth(c);
}
void updatedepth(struct node * p)                //UPDATING THE DEPTH OF EACH NODE WHEN ANOTHER NODE IS ADDED TO IT
{
p->leftdepth=maxdepth(p->left)+1;
p->rightdepth=maxdepth(p->right)+1;
}
struct node * search (int x,struct node * r)    //SEARCHING THE TREE FOR THE APPROPRIATE PLACE TO ATTACH
{                                                //THE INCOMING NODE CONTAINING A NEW NUMBER
while (1)
{
if (r==NULL)                            //IF EMPTY TREE
return NULL;
else
{
if (x==r->data)                        //IF NEW NO. IS SAME AS NUMBER IN THE ROOT
break;
else if(x>r->data)                    //IF NEW NO. IS GREATER THAN THE NO. IN THE CURRENT NODE
{
if(r->right==NULL) break ;
else return search (x,r->right);//RECURSIVE CALLS TO FUNCTION SEARCH
}
else                                //IF NEW NO IS LESS THAT THE THE NO. IN THE CURRENT NODE
{
if (r->left==NULL)      break;
else return search(x,r->left);    //RECURSIVE CALLS TO FUNCTION SEARCH
}
}
}
return r;                //RETURNING THE POINTER TO THE REQUIRED NODE WHERE THE NEW NODE IS TO BE ATTACHED
}
void output()        //FUNCTION TO DISPLAY THE DEPTH
{
cout<<"\n\t**********************************************************";
cout<<"\n\t\tDEPTH OF AVL TREE FORMED IS\t "<<maxdepth(root)<<endl;
}
};
void  main ()                    //MAIN FUNCTION
{
tree t;                        //CREATING AN OBJECT OF TYPE TREE
int i;
FILE *ifp;
ifp=fopen("int.txt","w");    //OPENING FILE TO WRITE 10000 INTEGERS
srand(17);                    //SETS THE RANDOM NUMBER SEED FOR THE RAND FUNCTION

for(i=0;i<10000;i++)        //LOOP TO GENERATE 10000 INTEGERS  AND WRITE INTO THE TEXT FILE
{
fprintf(ifp,"%d\n",rand());        //WRITING RANDOM NUMBERS TO THE FILE
};
cout<<"\t***THE FOLLOWING NUMBERS ARE REPEATED IN THE AVL TREE***\n\n";
t.input();                    //CALLING FUNCTION TO READ RANDON NOS.,GENERATE AVL TREE AND KEEP TRACK OF ITS DEPTH
t.output();                    //CALLING FUNCTION TO DISPLAY THE DEPTH OF THE AVL TREE
}//END OF PROGRAM