0

I am getting error in the creation of my AVL tree,the output of my code is giving infinite loop every time.

In the following code mknode function is used to create a node and lr,rl,right,leftfunctions are used to do the required rotations whereas insert function is used to insert the values in the AVL tree and then perform the rotations as per the requirement.

I had checked my code many times but was unable to find the mistake.

Please help me.

struct node
{int a;
struct node *left,*right;
int height;
}*root;
 int bal_factor(struct node*);
 int height(struct node*);
 int greater(int,int);
 struct node*mknode(int);
 struct node*insert(struct node*,int);
 struct node*left(struct node*);
 struct node*right(struct node*);
 struct node*lr(struct node*);
 struct node*rl(struct node*);
 void inorder(struct node*);
 void main()
{
printf("avl tree\n");
root=insert(root,30);
root=insert(root,40);
root=insert(root,20);
root=insert(root,10);
root=insert(root,45);
inorder(root);
}
void inorder(struct node *temp)
{
if(temp==NULL)
    return;
inorder(temp->left);
printf("%d\t",temp->a);
inorder(temp->right);
}
int bal_factor(struct node *temp)
{
if(temp==NULL)
    return 0;
else
 return(height(temp->left)-height(temp->right));
}
int height(struct node *temp)
{
if(temp==NULL)
    return 0;
else
    return greater(height(temp->left),height(temp->right))+1;

}
int greater(int a,int b)
{
if(a>b)
    return a;
else
    return b;
}
struct node* mknode(int t)
{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->a=t;
temp->left=temp->right=NULL;
temp->height=1;
return temp;
};
struct node*right(struct node *temp)
{struct node* temp1;
temp1=temp->left;
temp->left=temp1->right;
temp1->right=temp;
temp1->height=greater(height(temp1->left),height(temp1->right))+1;
temp->height=greater(height(temp->left),height(temp->right))+1;
return temp1;
};
struct node* left(struct node *temp)
{   struct node* temp1;
temp1=temp->right;
temp->right=temp1->left;
temp1->left=temp;
temp1->height=greater(height(temp1->left),height(temp1->right))+1;
temp->height=greater(height(temp->left),height(temp->right))+1;
return temp1;
};
struct node* lr(struct node *temp)
{
temp->left=left(temp->left);
return right(temp);
};
struct node* rl(struct node *temp)
{
temp->right=right(temp->right);
return left(temp);
};
struct node* insert(struct node *temp,int t1)
{
if(temp==NULL)
    return mknode(t1);
if(t1<temp->a)
    temp->left=insert(temp->left,t1);
else
    temp->right=insert(temp->right,t1);
int t;
temp->height=greater(height(temp->left),height(temp->right))+1;
t=bal_factor(temp);
if(t>1&&t1<temp->left->a);
return right(temp);
if(t1<-1&&t1>temp->right->a);
return left(temp);
if(t<-1&&t1<temp->right->a);
return rl(temp);
if(t>1&&t1>temp->left->a);
return lr(temp);

return temp;
}
Patrick
  • 331
  • 3
  • 18
Harsh
  • 70
  • 7

1 Answers1

1

This is wrong:

  if (t>1 && t1<temp->left->a);
  return right(temp);
  if (t1<-1 && t1>temp->right->a);
  return left(temp);
  if (t<-1 && t1<temp->right->a);
  return rl(temp);
  if (t>1 && t1>temp->left->a);
  return lr(temp);

You probably wanted this:

  if (t>1 && t1<temp->left->a)
    return right(temp);
  if (t1<-1 && t1>temp->right->a)
    return left(temp);
  if (t<-1 && t1<temp->right->a)
    return rl(temp);
  if (t>1 && t1>temp->left->a)
    return lr(temp);

Note the absence of ; after the lines starting with if.

Unrelated:

temp = (struct node*)malloc(sizeof(struct node));

should be written

temp = malloc(sizeof(struct node));

You don't cast the return value of malloc in C.

Jabberwocky
  • 48,281
  • 17
  • 65
  • 115
  • if we use temp = malloc(sizeof(struct node)); than it would return void pointer which has to be typecasted into struct node type pointer. – Harsh Oct 20 '17 at 10:21
  • @Harsh for an explanation [read this](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). – Jabberwocky Oct 20 '17 at 10:23
  • by the way thank u for helping me now my code is generating the right output – Harsh Oct 20 '17 at 10:24
  • @Harsh I almost fogot: you should indent your code correctly. – Jabberwocky Oct 20 '17 at 10:26
  • Actually sir I don't know how to write a code with proper indentation,that's why there was a problem with my code.Sir I will be highly grateful to you if you tell me how to write a proper indented code. – Harsh Oct 20 '17 at 11:02