Thread: AVL TREE implementation

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2013
Posts
1
Rep Power
0

AVL TREE implementation

Dear friends well at university i wrote this implementation of avl tree like 7 years ago and i wanted to share it with you...the problem is that i almost forget much aspects of what i wrote because of the 7 years but i thought it would be cool to share it after all these years

Code:
```	# include<stdio.h>
# include<stdlib.h>
typedef struct tree_pointer
{
int data;
struct tree_pointer *left,*right;
};
int balance_factor(struct tree_pointer *t);
void inorder_display(struct tree_pointer *t)
{
if(t)
{
inorder_display(t->left) ;
printf("%d\t",t->data);
printf("Balance factor of %d is (%d)\t",t->data,balance_factor(t));
inorder_display(t->right);
}
}

struct tree_pointer* bst_searching(struct tree_pointer *t,int x )
{
if(!t)
return NULL;
else
{
if(x==t->data)
return t;

else
if(x<t->data)
return bst_searching(t->left, x );
else
return bst_searching(t->right, x );
}
}

int tree_high(struct tree_pointer *t)
{
int right,left;
if (t!=NULL)
{
right = tree_high(t->right);
right++;
left = tree_high(t->left);
left++;

if ( left >=right)
return left;
else
return right;
}
else
return -1;
}

int balance_factor(struct tree_pointer *t)
{
int l,r;
l=tree_high(t->left);
r=tree_high(t->right);
return l-r;
}

/************************************************************DELETION*/
/************************************************************DELETION*/
/************************************************************DELETION*/
int bst_delete(struct tree_pointer **t,int x)
{
int i;
struct tree_pointer *p,*pp,*s,*ps,*c,*v[100];
p=*t;
pp=NULL;
i=0;
while(p && p->data!=x)
{
pp=p;
v[i]=p;
i++;

if(x<p->data)
p=p->left;
else
p=p->right;
}

if(p==NULL)
{
printf("null\n");
return 0;
}
if(p->left!=NULL && p->right!=NULL)
{
v[i]=p;
i++;
s=p->left;
ps=p;

while(s->right)
{
ps=s;
v[i]=s;
s=s->right;
printf("v[%d]=%d",i,v[i]);
printf("v[%d]->date =%d \n",i,v[i]->data);
i++;

}

p->data=s->data;
p=s;
pp=ps;

}
if(p->right==NULL)
{
c=p->left;
v[i]=c;

}
else
if (p->left==NULL)
{
c=p->right;
v[i]=c;

}

if (p==(*t))
(*t)=c;
if(p==pp->left)
pp->left=c;

else
pp->right=c;
if(c==NULL)
i--;

free (p);

p=pp=NULL;
while (i>=0)
{

if (balance_factor(v[i]) == 2 && ((balance_factor(v[i]->left)== 0) || (balance_factor(v[i]->left)==1)) )
{
p=v[i]->left;
v[i]->left=p->right;
p->right=v[i];

if (i!=0)
{
if(v[i-1]->left==v[i])
v[i-1]->left=p;
else
v[i-1]->right=p;
}
else
*t=p;

}
else
if ((balance_factor(v[i]) == 2) && balance_factor(v[i]->left)== -1)
{
p=v[i]->left;
pp=p->right;
p->right =pp->left;
v[i]->left=pp->right;
pp->right=v[i];
pp->left=p;
if (i!=0)
{
if (v[i-1]->right==v[i])
v[i-1]->right=pp;
else
v[i-1]->left=pp;
}
else
*t=pp;

}

else
if ((balance_factor(v[i]) == -2) && (balance_factor(v[i]->right)== 0 || balance_factor(v[i]->right)==-1) )
{
p=v[i]->right;
v[i]->right=p->left;
p->left=v[i];

if (i!=0)
{
if(v[i-1]->left==v[i])
v[i-1]->left=p;
else
v[i-1]->right=p;
}
else
*t=p;
}
else
if ((balance_factor(v[i]) == -2) && balance_factor(v[i]->right)== 1)
{
p=v[i]->right;
pp=p->left;
p->left =pp->right;
v[i]->right=pp->left;
pp->right=p;
pp->left=v[i];
if (i!=0)
{
if (v[i-1]->right==v[i])
v[i-1]->right=pp;
else
v[i-1]->left=pp;
}
else
*t=pp;

}
i--;

}

return 0;
}

/********************************************************************INSERTION*/
/********************************************************************INSERTION*/
int insert(struct tree_pointer **t,int v)
{
int r,i=0,l=0;
struct tree_pointer *p,*oldp,*x[50];
p=*t;

if (*t==NULL)
{
(*t)=(struct tree_pointer *)malloc(sizeof(struct tree_pointer));
(*t)->data=v;
(*t)->left=(*t)->right=NULL;
}

while (p!=NULL)
{
x[i]=p;
i++;
if ( v >p->data)
{
oldp=p;
r=0;
p=p->right;
}
else
{
oldp=p;
r=1;
p=p->left;
}

}
if(i>=1)
{
p=(struct tree_pointer *)malloc(sizeof(struct tree_pointer));
p->data=v;
p->left=p->right = NULL;
x[i]=p;
if (r==0)
oldp->right = p;
else
oldp->left = p;
}

if(i>=2)
{
i=i-2;
while (i>=0)
{

if ((balance_factor(x[i]) == 2) && (x[i+1]->left == x[i+2]))
{
x[i]->left=x[i+1]->right;
x[i+1]->right=x[i];

if (i!=0)
{
if(x[i-1]->left==x[i])
x[i-1]->left=x[i+1];
else
x[i-1]->right=x[i+1];
}
else
*t=x[i+1];
l=1;
}
else
if ((balance_factor(x[i]) == 2) && (x[i+1]->right == x[i+2]))
{
x[i+1]->right=x[i+2]->left;
x[i]->left=x[i+2]->right;
x[i+2]->left=x[i+1];
x[i+2]->right=x[i];
if (i!=0)
{
if (x[i-1]->right==x[i])
x[i-1]->right=x[i+2];
else
x[i-1]->left=x[i+2];
}
else
*t=x[i+2];
l=1;
}

else
if ((balance_factor(x[i]) == -2) && (x[i+1]->right == x[i+2]))
{
x[i]->right=x[i+1]->left;
x[i+1]->left=x[i];
if(i!=0)
{
if(x[i-1]->right==x[i])
x[i-1]->right=x[i+1];
else
x[i-1]->left=x[i+1];
}
else
*t=x[i+1];
l=1;
}
else
if ((balance_factor(x[i]) == -2) && (x[i+1]->left == x[i+2]))
{
x[i]->right=x[i+2]->left;
x[i+1]->left=x[i+2]->right;
x[i+2]->left=x[i];
x[i+2]->right=x[i+1];
if(i!=0)
{
if(x[i-1]->right==x[i])
x[i-1]->right=x[i+2];
else
x[i-1]->left=x[i+2];
}
else
*t=x[i+2];
l=1;
}

i--;
if(l==1)
return 0;
}

}
return 0;
}

void main()
{
struct tree_pointer *t=NULL,*z=NULL;
int n,v,m,j,d;
printf("Enter the values contained in the tree (when u want to stop press -1):");

scanf("%d",&v);

while (v!=-1)
{
insert(&t,v);
scanf("%d",&v);
}
do
{
printf("\t\t\t Available List:\n");
printf("\t\t\t 1 --> Insert in bst\n");
printf("\t\t\t 2 --> Inorder display of bst\n");
printf("\t\t\t 3 --> Delete\n");
printf("\t\t\t 4 --> Search for target value\n");
scanf("%d",&d);
}
while (d!=1 && d!=2 && d!=3 &&  d!=4 );
switch(d)
{
case 1:
printf("Enter the value you want to insert: ");
scanf("%d",&n);
insert(&t,n);
printf("The inorder display after insertion is:\n");
inorder_display(t);
break;
case 2:
printf("The inorder display is:\n");
inorder_display (t);
break;
case 3:
printf("Enter the value you want to delete: ");
scanf("%d",&m);
bst_delete(&t,m);
printf("The inorder display after deletion is:\n");
inorder_display(t);

break;
case 4:
printf("enter the number you want to search for\n");
scanf("%d",&j);
z=bst_searching(t,j);
printf("the address of the target is :%d ",z);

break;
default:
printf("Not Valid CHOICE!!");
}
printf("\n");

}```
BTW this code has been wrote and compiled under Borland C++.
2. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Code tags will make your code easier to read:

http://forums.devshed.com/misc.php?do=bbcode#code

Edit your original post, strip out the mess that's supposed to be source code, drop the open and closing code tags in there, then copy your source code directly from your source editor in between the tags. That will preserve the formatting and make it readable.

Read the sticky notes at the top of this forum!

Comments on this post

• SimonB2 agrees
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2013
Posts
40
Rep Power
19
Thank you for sharing!