The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."
The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. AVL trees perform better than red-black trees for lookup-intensive applications. The AVL tree balancing algorithm appears in many computer science curricula.
----------------------------------------------------------------------------------------------
A C PROGRAM TO IMPLEMENT OPERATIONS IN AVL TREE
COMPILER EMPLOYED: DEV C++ COMPILER-4.9.9.2 
SOURCE FILE SIZE :5 kb
EXE FILE SIZE :4 kb
NOTE: PLEASE INCLUDE THE DESIRED HEADER FILE
---------------------------------------------------------------------------------------------
C PROGRAM SOURCE & EXE DOWNLOAD:
Click download button to download
DISCLAIMER: The following program cannot be ensured of perfection.so any flaws in the program can be notified in the comments section.
----------------------------------------------------------------------------------------------
CODE:
#include
typedef enum { FALSE ,TRUE } bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
};
struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);
main()
{
bool ht_inc;
int info ;
int OPT,CH;
struct node *root = (struct node *)malloc(sizeof(struct node));
root = NULL;
do
{
printf("\n AVL OPERATIONS BY DEPLOYMENT OF LINKED LISTS...");
printf("\n\n MENU:");
printf("\n[1].INSERT");
printf("\n[2].DISPLAY");
printf("\n[3].QUIT");
printf("\n\n ENTER OPTION:");
scanf("%d",&OPT);
switch(OPT)
{
case 1:
printf("\nINSERTION PROCESS INVOKED...");
printf("\n ENTER ELEMENT: ");
scanf("%d", &info);
if( search(root,info) == NULL )
root = insert(info, root, &ht_inc);
else
printf("\n DUPLICATE VALUE IGNORED...");
break;
case 2:
printf("\n DELETION PROCESS INVOKED...");
if(root==NULL)
{
printf("\nERROR!!!!! TREE IS EMPTY...");
continue;
}
printf("\nTREE :");
display(root, 1);
printf("\n\n");
printf("\nINORDER TRAVERSAL:");
inorder(root);
printf("\n");
break;
case 3:
exit(1);
default:
printf("\nINVALID CHOICE..");
}
printf("\n DO YOU WISH TO CONTINUE?1~0:");
scanf("%d",&CH);
}while(CH==1);
system("pause");
return 0;
}
struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
if(info <>info)
ptr=search(ptr->lchild,info);
else if( info > ptr->info)
ptr=search(ptr->rchild,info);
return(ptr);
}/*End of search()*/
struct node *insert (int info, struct node *pptr, int *ht_inc)
{
struct node *aptr;
struct node *bptr;
if(pptr==NULL)
{
pptr = (struct node *) malloc(sizeof(struct node));
pptr->info = info;
pptr->lchild = NULL;
pptr->rchild = NULL;
pptr->balance = 0;
*ht_inc = TRUE;
return (pptr);
}
if(info <>info)
{
pptr->lchild = insert(info, pptr->lchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case -1: /* Right heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = 1;
break;
case 1: /* Left heavy */
aptr = pptr->lchild;
if(aptr->balance == 1)
{
printf("Left to Left Rotation\n");
pptr->lchild= aptr->rchild;
aptr->rchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Left to right rotation\n");
bptr = aptr->rchild;
aptr->rchild = bptr->lchild;
bptr->lchild = aptr;
pptr->lchild = bptr->rchild;
bptr->rchild = pptr;
if(bptr->balance == 1 )
pptr->balance = -1;
else
pptr->balance = 0;
if(bptr->balance == -1)
aptr->balance = 1;
else
aptr->balance = 0;
bptr->balance=0;
pptr=bptr;
}
*ht_inc = FALSE;
}/*End of switch */
}/*End of if */
}/*End of if*/
if(info > pptr->info)
{
pptr->rchild = insert(info, pptr->rchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case 1: /* Left heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = -1;
break;
case -1: /* Right heavy */
aptr = pptr->rchild;
if(aptr->balance == -1)
{
printf("Right to Right Rotation\n");
pptr->rchild= aptr->lchild;
aptr->lchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Right to Left Rotation\n");
bptr = aptr->lchild;
aptr->lchild = bptr->rchild;
bptr->rchild = aptr;
pptr->rchild = bptr->lchild;
bptr->lchild = pptr;
if(bptr->balance == -1)
pptr->balance = 1;
else
pptr->balance = 0;
if(bptr->balance == 1)
aptr->balance = -1;
else
aptr->balance = 0;
bptr->balance=0;
pptr = bptr;
}/*End of else*/
*ht_inc = FALSE;
}/*End of switch */
}/*End of if*/
}/*End of if*/
return(pptr);
}/*End of insert()*/
display(struct node *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf("\n");
for (i = 0; i <>info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display()*/
inorder(struct node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);
}
}/*End of inorder()*/
Your's friendly,
[MOHANRAM.G],
ADMIN...
0 comments:
Post a Comment