IMPLEMENTATION OF AN AVL TREE
AIM :
To implement AVL tree.
ALGORITHM :
1. Start the program
2. Create a structure avlnode with element, left tree , right tree and height
3. Print “ 1.insert 2.find 3.display”
4. If ‘insert’ insert the given node into avl tree and check for the violation
5. If violation occurs do single or double rotation according to the need
6. Compute the height of the nodes during each insertion
7. If ‘find’ find the given element in the tree
8. If ‘display’ display the tree in inorder
9. Stop the program
SOURCE CODE :
#include
#include
struct avlnode;
typedef struct avlnode *ptr;
typedef ptr position;
typedef ptr avltree;
struct avlnode
{
int element;
avltree left;
avltree right;
int height;
};
static int height(position p)
{
if(p==NULL)
return -1;
else
return p->height;
}
avltree insert(int x,avltree t)
{
if(t==NULL)
{
//create and return a one node tree
t=malloc(sizeof(struct avlnode));
t->element=x;
t->height=0;
t->left=t->right=NULL;
}
else if(xelement)
{
t->left=insert(x,t->left);
if(height(t->left)-height(t->right)==2)
{
if(xleft->element)
{
t=singlerotatewithleft(t);
}
else
{
t=doublerotatewithleft(t);
}
}
}
else if(x>t->element)
{
t->right=insert(x,t->right);
if(height(t->right)-height(t->left)==2)
{
if(xright->element)
{
t=singlerotatewithright(t);
}
else
{
t=doublerotatewithright(t);
}
}
}
//else x is there in tree already. we do nothing
t->height=max(height(t->left),height(t->right))+1;
return t;
}
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
static position singlerotatewithleft(position k2)
{
position k1;
k1=k2->left;
k2->left=k1->right;
k1->right=k2;
k2->height=max(height(k2->left),height(k2->right))+1;
k1->height=max(height(k1->left),k2->height)+1;
return k1;
}
static position singlerotatewithright(position k2)
{
position k1;
k1=k2->right;
k2->right=k1->left;
k1->left=k2;
k2->height=max(height(k2->right),height(k2->left))+1;
k1->height=max(height(k1->right),k2->height)+1;
return k1;
}
static position doublerotatewithleft(position k3)
{
//rotate between k1 and k2
k3->left=singlerotatewithright(k3->left);
//rotate between k3 and k2
return singlerotatewithleft(k3);
}
static position doublerotatewithright(position k3)
{
//rotate between k1 and k2
k3->right=singlerotatewithleft(k3->right);
//rotate between k3 and k2
return singlerotatewithright(k3);
}
position find(int x,avltree t)
{
if(t==NULL)
return NULL;
if(xelement)
return find(x,t->left);
else if(x>t->element)
return find(x,t->right);
else
return t;
}
void display(avltree t)
{
if(t!=NULL)
{
display(t->left);
printf("\t%d\n",t->element);
display(t->right);
}
}
main()
{
int x,ch;
avltree t=NULL;
do
{
printf("\n1.Insert 2.Find 3.Display 4.exit\nEnter your choice:\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the element:\n");
scanf("%d",&x);
t=insert(x,t);
break;
case 2:
printf("Enter the element:\n");
scanf("%d",&x);
t=find(x,t);
if(t==NULL)
printf("Element not found");
else
printf("Element found",t->element);
break;
case 3:
display(t);
break;
case 4:
break;
}
}while(ch!=4);
}
OUTPUT :
1.insert 2.find 3.display 4.exit
Enter your choice : 1
Enter the element :5
1.insert 2.find 3.display 4.exit
Enter your choice : 1
Enter the element :3
1.insert 2.find 3.display 4.exit
Enter your choice : 1
Enter the element :1
1.insert 2.find 3.display 4.exit
Enter your choice : 1
Enter the element :2
1.insert 2.find 3.display 4.exit
Enter your choice : 5
Enter the element :3
Element found
1.insert 2.find 3.display 4.exit
Enter your choice : 3
1 2 3 5
1.insert 2.find 3.display 4.exit
Enter your choice : 4
Bye!!
RESULT :
Thus the c program to implement avl tree is written and executed successfully.
Earn upto Rs. 9,000 pm checking Emails. Join now!
No comments:
Post a Comment