C code to implement AVL Tree

AVL tree(Adelson-Velskii and Ladis'tree, named after their inventors) is also called balanced binary tree. Property of AVL tree: the hieght of the two child subtree of any node differ by at most one.If they differ by more than one, re-balancing is done to restore this property.

/* C program to implement AVL Tree */

#include<stdio.h>
#include<malloc.h>

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 choice;
    struct node *root = (struct node *)malloc(sizeof(struct node));
    root =  NULL;

    while(1)
    {
        printf("1.Insert\n");
        printf("2.Display\n");
        printf("3.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            printf("Enter the value to be inserted : ");
            scanf("%d", &info);
            if( search(root,info) == NULL )
                root = insert(info, root, &ht_inc);
            else
                printf("Duplicate value ignored\n");
            break;
        case 2:
            if(root==NULL)
            {
                printf("Tree is empty\n");
                continue;
            }
            printf("Tree is :\n");
            display(root, 1);
            printf("\n\n");
            printf("Inorder Traversal is: ");
            inorder(root);
            printf("\n");
            break;
        case 3:
            exit(1);
        default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

struct node* search(struct node *ptr,int info)
{
    if(ptr!=NULL)
        if(info < ptr->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 < pptr->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 < level; i++)
            printf("    ");
        printf("%d", ptr->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()*/

/* Output of AVL Tree Program */

Output of AVL Tree Program

Output of AVL Tree Program

For more related to Data Structure check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.